Aims To understand whether the variability found in the proteome of Helicobacter pylori relates to the genomic methylation, virulence and associated gastric disease. Methods and Results We applied the Minimum-Common-Restriction-Modification (MCRM) algorithm to genomic methylation data of 30 Portuguese H.pylori strains, obtained by genome sensitivity to Type II restriction enzymes' digestion. All the generated dendrograms presented three clusters with no association with gastric disease. Comparative analysis of two-dimensional gel electrophoresis (2DE) maps obtained for total protein extracts of 10 of these strains, representative of the three main clusters, revealed that among 70 matched protein spots (in a universe of 300), 16 were differently abundant (P<0 center dot 05) among clusters. Of these, 13 proteins appear to be related to the cagA genotype or gastric disease. The abundance of three protein species, DnaK, GlnA and HylB, appeared to be dictated by the methylation status of their gene promoter. Conclusions Variations in the proteome profile of strains with common geographic origin appear to be related to differences in cagA genotype or gastric disease, rather than to clusters organized according to strain genomic methylation. Significance and Impact of the Study The simultaneous study of the genomic methylation and proteome is important to correlate epigenetic modifications with gene expression and pathogen virulence.