This study assessed the diversity of the enterohemorrhagic Escherichia coli (EHEC) hemolysin gene (ehxA) in a variety of Shiga toxin-producing E. coli (STEC) serotypes and the relationship between ehxA types and virulence markers on the locus for enterocyte effacement (LEE). Restriction fragment length polymorphism of the ehxA gene and flanking sequences and of the E. coli attaching and effacing (eae) gene was determined for 79 EHEC hemolysin-positive STEC isolates of 37 serotypes. Two main groups of EHEC hemolysin sequences and associated plasmids, which corresponded to the eae-positive and the eae-negative isolates, were delineated. Comparisons of the ehxA gene sequences of representative isolates of each group showed that this gene and the rest of the EHEC hemolysin operon are highly conserved. Digestion of an ehxA PCR product with the restriction endonuclease TaqI showed a unique restriction pattern for eae-negative isolates and another one for isolates of serotypes O157:H7 and O157:NM. A conserved fragment of 5.6 kb with four potential open reading frames was identified on the EHEC hemolysin plasmid of eae-positive STEC. Phylogenetic analysis of a subset of 27 STEC isolates, one enteropathogenic E. coli isolate, and a K-12 reference isolate showed that eae-positive STEC isolates all belong to a single evolutionary lineage and that the EHEC hemolysin plasmid and the ehxA gene evolved within this lineage without recent horizontal transfer. However, the eae gene and the LEE appear to have been transferred horizontally within this STEC lineage on several occasions. The reasons for the lack of transfer or maintenance of the LEE in other STEC lineages are not clear and require further study.