Shiga toxin-producing Escherichia coli (STEC) belonging to certain serogroups (e.g., O157 and O26) can cause serious conditions like hemolytic-uremic syndrome (HUS), but other strains might be equally pathogenic. While virulence factors, like stx and eae, have been well studied, little is known about the prevalence of the E. coli hemolysin genes (hlyA, ehxA, e-hlyA, and sheA) in association with these factors. Hemolysins are potential virulence factors, and ehxA and hlyA have been associated with human illness, but the significance of sheA is unknown. Hence, 435 E. coli strains belonging to 62 different O serogroups were characterized to investigate gene presence and phenotypic expression of hemolysis. We further investigated ehxA subtype patterns in E. coli isolates from clinical, animal, and food sources. While sheA and ehxA were widely distributed, e-hlyA and hlyA were rarely found. Most strains (86.7%) were hemolytic, and significantly more hemolytic (95%) than nonhemolytic strains (49%) carried stx and/or eae (P < 0.0001). ehxA subtyping, as performed by using PCR in combination with restriction fragment length polymorphism analysis, resulted in six closely related subtypes (>94.2%), with subtypes A/D being eae-negative STECs and subtypes B, C, E, and F eae positive. Unexpectedly, ehxA subtype patterns differed significantly between isolates collected from different sources (P < 0.0001), suggesting that simple linear models of exposure and transmission need modification; animal isolates carried mostly subtypes A/C (39.3%/42.9%), food isolates carried mainly subtype A (81.9%), and clinical isolates carried mainly subtype C (66.4%). Certain O serogroups correlated with particular ehxA subtypes: subtype A with O104, O113, and O8; B exclusively with O157; C with O26, O111, and O121.