Enterohemorrhagic Escherichia coli (EHEC) O157:H7 strains are major human food-borne pathogens, responsible for bloody diarrhea and hemolytic-uremic syndrome worldwide. Thus far, there is no vaccine for humans against EHEC infections. In this study, a comparative genomics analysis was performed to identify EHEC-specific antigens useful as potential vaccines. The genes present in both EHEC EDL933 and Sakai strains but absent in nonpathogenic E. coli K-12 and HS strains were subjected to an in silico analysis to identify secreted or surface-expressed proteins. We obtained a total of 65 gene-encoding protein candidates, which were subjected to immunoinformatics analysis. Our criteria of selection aided in categorizing the candidates as high, medium, and low priority. Three members of each group were randomly selected and cloned into pVAX-1. Candidates were pooled accordingly to their priority group and tested for immunogenicity against EHEC O157:H7 using a murine model of gastrointestinal infection. The high-priority (HP) pool, containing genes encoding a Lom-like protein (pVAX-31), a putative pilin subunit (pVAX-12), and a fragment of the type III secretion structural protein EscC (pVAX-56.2), was able to induce the production of EHEC IgG and sIgA in sera and feces. HP candidate-immunized mice displayed elevated levels of Th2 cytokines and diminished cecum colonization after wild-type challenge. Individually tested HP vaccine candidates showed that pVAX-12 and pVAX-56.2 significantly induced Th2 cytokines and production of fecal EHEC sIgA, with pVAX-56.2 reducing EHEC cecum colonization. We describe here a bioinformatics approach able to identify novel vaccine candidates potentially useful for preventing EHEC O157:H7 infections.