DNA sequence-based molecular subtyping methods such as multilocus sequence typing (MLST) are commonly used to generate phylogenetic inferences for monomorphic pathogens. The development of an effective MLST scheme for subtyping Escherichia coli O157:H7 has been hindered in the past due to the lack of sequence variation found within analyzed housekeeping and virulence genes. A recent study suggested that rhs genes are under strong positive selection pressure, and therefore in this study we analyzed these genes within a diverse collection of E. coli O157:H7 strains for sequence variability. Eighteen O157:H7 strains from lineages I and II and 15 O157:H7 strains from eight clades were included. Examination of these rhs genes revealed 44 polymorphic loci (PL) and 10 sequence types (STs) among the 18 lineage strains and 280 PL and 12 STs among the 15 clade strains. Phylogenetic analysis using rhs genes generally grouped strains according to their known lineage and clade classifications. These findings also suggested that O157:H7 strains from clades 6 and 8 fall into lineage I/II and that strains of clades 1, 2, 3, and 4 fall into lineage I. Additionally, unique markers were found in rhsA and rhsJ that might be used to define clade 8 and clade 6. Therefore, rhs genes may be useful markers for phylogenetic analysis of E. coli O157:H7.