Enterohemorrhagic Escherichia coli (EHEC) is the causative agent of bloody diarrhea and extraintestinal sequelae in humans, most importantly hemolytic-uremic syndrome (HUS) and thrombotic thrombocytopenic purpura (TTP). Besides the bacteriophage-encoded Shiga toxin gene (stx), EHEC harbors the locus of enterocyte effacement (LEE), which confers the ability to cause attaching and effacing lesions. Currently, the vast majority of EHEC infections are caused by strains belonging to five O serogroups (the "big five"), which, in addition to O157, the most important, comprise O26, O103, O111, and O145. We hypothesize that these four non-O157 EHEC serotypes differ in their phylogenies. To test this hypothesis, we used multilocus sequence typing (MLST) to analyze a large collection of 250 isolates of these four O serogroups, which were isolated from diseased as well as healthy humans and cattle between 1952 and 2009. The majority of the EHEC isolates of O serogroups O26 and O111 clustered into one sequence type complex, STC29. Isolates of O103 clustered mainly in STC20, and most isolates of O145 were found within STC32. In addition to these EHEC strains, STC29 also included stx-negative E. coli strains, termed atypical enteropathogenic E. coli (aEPEC), yet another intestinal pathogenic E. coli group. The finding that aEPEC and EHEC isolates of non-O157 O serogroups share the same phylogeny suggests an ongoing microevolutionary scenario in which the phage-encoded Shiga toxin gene stx is transferred between aEPEC and EHEC. As a consequence, aEPEC strains of STC29 can be regarded as post- or pre-EHEC isolates. Therefore, STC29 incorporates phylogenetic information useful for unraveling the evolution of EHEC.