Infection of the stomach byHelicobacter pyloriis ubiquitous among humans. However, althoughH. pyloristrains from different geographic areas are associated with clear phylogeographic differentiation1-4, the age of an association between these bacteria with humans remains highly controversial5,6. Here we show, using sequences from a large data set of bacterial strains that, as in humans, genetic diversity inH. pyloridecreases with geographic distance from east Africa, the cradle of modern humans. We also observe similar clines of genetic isolation by distance (IBD) for bothH. pyloriand its human host at a worldwide scale. Like humans, simulations indicate thatH. pyloriseems 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 inH. pylorifrom Europe strongly resemble the classical clines for Europeans described by Cavalli-Sforza and colleagues7. Taken together, our results establish that anatomically modern humans were already infected byH. pyloribefore their migrations from Africa and demonstrate thatH. pylorihas remained intimately associated with their human host populations ever since.