Helicobacter pylori is the principal cause of gastric cancer, the second leading cause of cancer mortality worldwide. However, H. pylori prevalence generally does not predict cancer incidence. To determine whether coevolution between host and pathogen influences disease risk, we examined the association between the severity of gastric lesions and patterns of genomic variation in matched human and H. pylori samples. Patients were recruited from two geographically distinct Colombian populations with significantly different incidences of gastric cancer, but virtually identical prevalence of H. pylori infection. All H. pylori isolates contained the genetic signatures of multiple ancestries, with an ancestral African cluster predominating in a low-risk, coastal population and a European cluster in a high-risk, mountain population. The human ancestry of the biopsied individuals also varied with geography, with mostly African ancestry in the coastal region (58%), and mostly Amerindian ancestry in the mountain region (67%). The interaction between the host and pathogen ancestries completely accounted for the difference in the severity of gastric lesions in the two regions of Colombia. In particular, African H. pylori ancestry was relatively benign in humans of African ancestry but was deleterious in individuals with substantial Amerindian ancestry. Thus, coevolution likely modulated disease risk, and the disruption of coevolved human and H. pylori genomes can explain the high incidence of gastric disease in the mountain population.