Enterohemorrhagic Escherichia coli O157:H7, a world-wide human food-borne pathogen, causes mild to severe diarrhea, hemorrhagic colitis, and hemolytic uremic syndrome. The ability of this pathogen to persist in the environment contributes to its dissemination to a wide range of foods and food processing surfaces. Biofilms are thought to be involved in persistence, but the process of biofilm formation is complex and poorly understood in E. coli O157:H7. To better understand the genetics of this process, a mini-Tn5 transposon insertion library was constructed in strain EDL933 and screened for biofilm-negative mutants using a microtiter plate assay. Ninety-five of 11,000 independent insertions (0.86%) were biofilm negative, and transposon insertions were located in 51 distinct genes/intergenic regions that must be involved either directly or indirectly in biofilm formation. All of the 51 biofilm-negative mutants showed reduced biofilm formation on both hydrophilic and hydrophobic surfaces. Thirty-six genes were unique to this study, including genes on the virulence plasmid pO157. The type V secreted autotransporter serine protease EspP and the enterohemolysin translocator EhxD were found to be directly involved in biofilm formation. In addition, EhxD and EspP were also important for adherence to T84 intestinal epithelial cells, suggesting a role for these genes in tissue interactions in vivo.