Enterohemorrhagic Escherichia coli (EHEC) is a food-borne cause of bloody diarrhea and the hemolyticuremic syndrome (HUS) in humans. Most strains of EHEC belong to a group of bacterial pathogens that cause distinctive lesions on the host intestine termed attaching-and-effacing (A/E) lesions. A/E strains of EHEC, including the predominant serotype, O157:H7, are responsible for the majority of HUS outbreaks worldwide. However, several serotypes of EHEC are not A/E pathogens because they lack the locus of enterocyte effacement (LEE) pathogenicity island. Nevertheless, such strains have been associated with sporadic cases and small outbreaks of hemorrhagic colitis and HUS. Of these LEE-negative organisms, O113:H21 is one of the most commonly isolated EHEC serotypes in many regions. Clinical isolates of LEE-negative EHEC typically express Shiga toxin 2 and carry an ∼90-kb plasmid that encodes EHEC hemolysin, but in the absence of LEE, little is known about the way in which these pathogens colonize the host intestine. In this study we describe the identification of a novel fimbrial gene cluster related to long polar fimbriae in EHEC O113:H21. This chromosomal region comprises four open reading frames, lpfA to lfpD, and has the same location in the EHEC O113:H21 genome as O island 154 in the prototype EHEC O157:H7 strain, EDL933. In a survey of EHEC of other serotypes, homologues of lpfAO113 were found in 26 of 28 LEE-negative and 8 of 11 non-O157:H7 LEE-positive EHEC strains. Deletion of the putative major fimbrial subunit gene, lpfA, from EHEC O113:H21 resulted in decreased adherence of this strain to epithelial cells, suggesting that lpfO113 may function as an adhesin in LEE-negative isolates of EHEC.