Enterohemorrhagic Escherichia coli (EHEC) was first recognized as a cause of human disease in 1983 and is associated with diarrhea and hemorrhagic colitis, which may be complicated by life-threatening renal and neurological sequelae. EHEC are defined by their ability to produce one or more Shiga-like toxins (Stx), which mediate the systemic complications of EHEC infections, and to induce characteristic attaching and effacing lesions on intestinal epithelia, a phenotype that depends on the locus of enterocyte effacement. Acquisition of Stx-encoding bacteriophages by enteropathogenic E. coli is believed to have contributed to the evolution of EHEC, and consequently some virulence factors are conserved in both pathotypes. A key requirement for E. coli to colonize the intestines and produce disease is the ability to adhere to epithelial cells lining the gastrointestinal tract. Here, we review knowledge of the adhesins produced by EHEC and other Stx-producing E. coli , with emphasis on genetic, structural, and mechanistic aspects and their contribution to pathogenesis.