Helicobacter pylori is the strongest known risk factor for gastric adenocarcinoma, yet only a fraction of infected persons ever develop cancer. The extensive genetic diversity inherent to this pathogen has precluded comprehensive analyses of constituents that mediate carcinogenesis. We previously reported that in vivo adaptation of a non-carcinogenic H. pylori strain endowed the output derivative with the ability to induce adenocarcinoma, providing a unique opportunity to identify proteins selectively expressed by an oncogenic H. pylori strain. Using a global proteomics DIGE/MS approach, a novel missense mutation of the flagellar protein FlaA was identified that affects structure and function of this virulence-related organelle. Among 25 additional differentially abundant proteins, this approach also identified new proteins previously unassociated with gastric cancer, generating a profile of H. pylori proteins to use in vaccine development and for screening persons infected with strains most likely to induce severe disease.