Vaccination is the most effective method to prevent infectious diseases. However, approaches to identify novel vaccine candidates are commonly laborious and protracted. While surface proteins are suitable vaccine candidates and can elicit antibacterial antibody responses, systematic approaches to define surfomes from gram-negatives have rarely been successful. Here we developed a combined discovery-driven mass spectrometry and computational strategy to identify bacterial vaccine candidates and validate their immunogenicity using a highly prevalent gram-negative pathogen, Helicobacter pylori, as a model organism. We efficiently isolated surface antigens by enzymatic cleavage, with a design of experiment based strategy to experimentally dissect cell surface-exposed from cytosolic proteins. From a total of 1,153 quantified bacterial proteins, we thereby identified 72 surface exposed antigens and further prioritized candidates by computational homology inference within and across species. We next tested candidate-specific immune responses. All candidates were recognized in sera from infected patients, and readily induced antibody responses after vaccination of mice. The candidate jhp_0775 induced specific B and T cell responses and significantly reduced colonization levels in mouse therapeutic vaccination studies. In infected humans, we further show that jhp_0775 is immunogenic and activates IFNγ secretion from peripheral CD4+ and CD8+ T cells. Our strategy provides a generic preclinical screening, selection and validation process for novel vaccine candidates against gram-negative bacteria, which could be employed to other gram-negative pathogens.