Among the various pathogenic Escherichia coli strains, enterohemorrhagic E. coli (EHEC) is the most devastating. Although serotype O157:H7 strains are the most prevalent, strains of different serotypes also possess similar pathogenic potential. Here, we present the results of a genomic comparison between EHECs of serotype O157, O26, O111, and O103, as well as 21 other, fully sequenced E. coli/Shigella strains. All EHECs have much larger genomes (5.5-5.9 Mb) than the other strains and contain surprisingly large numbers of prophages and integrative elements (IEs). The gene contents of the 4 EHECs do not follow the phylogenetic relationships of the strains, and they share virulence genes for Shiga toxins and many other factors. We found many lambdoid phages, IEs, and virulence plasmids that carry the same or similar virulence genes but have distinct evolutionary histories, indicating that independent acquisition of these mobile genetic elements has driven the evolution of each EHEC. Particularly interesting is the evolution of the type III secretion system (T3SS). We found that the T3SS of EHECs is composed of genes that were introduced by 3 different types of genetic elements: an IE referred to as the locus of enterocyte effacement, which encodes a central part of the T3SS; SpLE3-like IEs; and lambdoid phages carrying numerous T3SS effector genes and other T3SS-related genes. Our data demonstrate how E. coli strains of different phylogenies can independently evolve into EHECs, providing unique insights into the mechanisms underlying the parallel evolution of complex virulence systems in bacteria.