Helicobacter pylori is associated with severe gastroduodenal disorders but is also a bacterial genetic marker of human migrations. First, we provide evidence that distinct H. pylori genetic populations accompanied at least four ancient human migrations into Oceania and Southeast Asia: i) an expansion of Austronesian speaking people about 5000 years ago from Taiwan into Oceania, ii) a migration from India into Southeast Asia within the last 2000 years, iii) a migration of Austro-Asiatic speaking people into Vietnam and Cambodia about 4000 years ago, and iv) a migration of the ancestors of the Thai people from Southern China into Thailand during the early second millennium AD. These findings demonstrate that H. pylori genetic diversity has more discriminatory power than traditional human genetic markers for tracing old human migrations. Second, we investigated virulence factors of H. pylori strains isolated from patients with gastric symptoms in Senegal and Cambodia. In Senegal, a significant association was observed between gastric cancer and the cagA gene, two EPIYA-C segments, and the s1 vacA allele in Senegal. Multiple EPIYA-C segments were less frequent than reported in other countries, possibly contributing to the low incidence of gastric cancer. In Cambodia, the frequent introgression of European vacA and cagA alleles into East Asian H. pylori strains was observed. As VacA and CagA have opposing effects, this expansion may disrupt the balancing activities on epithelial cells which might result in severe consequences for individual disease outcome.