Enterohemorrhagic E. coli (EHEC) is a major cause of large outbreaks worldwide associated with hemorrhagic colitis and hemolytic uremic syndrome. While vaccine development is warranted, a licensed vaccine, specific for human use, against EHEC is not yet available. In this study, the reverse vaccinology approach combined with genomic, transcriptional and molecular epidemiology data was applied on the EHEC O157:H7 genome to select new potential vaccine candidates. Twenty-four potential protein antigens were identified and one of them (MC001) was successfully expressed onto Generalized Modules for Membrane Antigens (GMMA) delivery system. GMMA expressing this vaccine candidate was immunogenic, raising a specific antibody response. Immunization with the MC001 candidate was able to reduce the bacterial load of EHEC O157:H7 strain in feces, colon and caecum tissues after murine infection. MC001 is homologue to lipid A deacylase enzyme (LpxR), and to our knowledge, this is the first study describing it as a potential vaccine candidate. Gene distribution and sequence variability analysis showed that MC001 is present and conserved in EHEC and in enteropathogenic E. coli (EPEC) strains. Given the high genetic variability among and within E. coli pathotypes, the identification of such conserved antigen suggests that its inclusion in a vaccine might represent a solution against major intestinal pathogenic strains.