Infection of the stomach by Helicobacter pylori is ubiquitous among humans. However, although H. pylori strains from different geographic areas are associated with clear phylogeographic differentiation, the age of an association between these bacteria with humans remains highly controversial. Here we show, using sequences from a large data set of bacterial strains that, as in humans, genetic diversity in H. pylori decreases with geographic distance from east Africa, the cradle of modern humans. We also observe similar clines of genetic isolation by distance (IBD) for both H. pylori and its human host at a worldwide scale. Like humans, simulations indicate that H. pylori seems to have spread from east Africa around 58,000 yr ago. Even at more restricted geographic scales, where IBD tends to become blurred, principal component clines in H. pylori from Europe strongly resemble the classical clines for Europeans described by Cavalli-Sforza and colleagues. Taken together, our results establish that anatomically modern humans were already infected by H. pylori before their migrations from Africa and demonstrate that H. pylori has remained intimately associated with their human host populations ever since.