The repetitive interspersed family (rif) and subtelomeric variable open reading frames (stevor) are highly diverse multi-gene families in the malaria parasite Plasmodium falciparum. Embedded on the surface of infected erythrocytes, RIFIN and STEVOR proteins are involved in cytoadherence and immune evasion, but the extent of family-wide sequence diversity across strains has yet to be comprehensively investigated in light of improved resolution of the subtelomeric genome sequences. Using a k-mer frequency approach, we analyzed long-read genomic sequence data from 18 geographically diverse P. falciparum genome assemblies, including lab strains and clinical isolates. We hypothesized that k-mer sequence comparison can identify existing RIFIN and STEVOR subgroups, identify novel subgroups, and generate more robust and reliable estimates of family-wide sequence diversity. Full-length RIFIN and STEVOR proteins shared on average 49.5% and 61.1% amino acid k-mer similarity, respectively, which fell to 25.1% and 20% in the hypervariable regions alone. Despite this diversity, we identified 11 RIFINs and five STEVORs that were conserved across strains above expected thresholds. A subset of these strain-transcendent genes was similar and syntenic to genes in related Plasmodium species, suggesting an ancient origin. Additionally, in silico structural predictions from AlphaFold showed that three-dimensional structures of RIFIN receptor-binding regions were more conserved than their sequences suggested. Evolutionarily constrained RIFINs and STEVORs may have critical functions in parasite survival or pathogenesis. This study provides a framework for investigating diversity in highly variable multi-gene families and highlights the potential of strain-transcendent RIFIN and STEVOR proteins as vaccine candidates.