Autotransporter (AT) proteins have been identified in many Gram-negative pathogens and are unique in that their primary sequence is sufficient to direct their transport across the bacterial membrane system. Where characterized they are uniformly associated with virulence. Using conserved AT motifs as a search tool, four putative AT proteins were identified in the Enterohemorrhagic Escherichia coli O157:H7 EDL933 genome. The genes encoding these proteins (z0402/ehaA, z0469/ehaB, z3487/ehaC and z3948/ehaD) were PCR amplified, cloned and expressed in an E. coli K-12 MG1655flu background. Preliminary characterization revealed that ehaA, ehaB and ehaD encode proteins associated with increased biofilm formation. One of these genes (ehaA) resides on a genomic island in E. coli O157:H7 strains EDL933 and Sakai. Over-expression of EhaA in E. coli K-12 demonstrated it is located at the cell surface and resulted in the formation of large cell aggregates, promoted significant biofilm formation and mediated adhesion to primary epithelial cells of the bovine terminal rectum. The expression of ehaA was demonstrated in E. coli EDL933 by RT-PCR. An EhaA-specific antibody revealed the EhaA protein was expressed in 24/50 generic Shiga toxin-producing E. coli (STEC) strains of various serotypes including O157:H7. However, the deletion of ehaA from E. coli EDL933 and a STEC strain from serotype O111:H(-) did not affect biofilm growth. Our results suggest that EhaA may contribute to adhesion, colonization and biofilm formation by E. coli O157:H7 and possibly other STEC serotypes.