The gastric bacterium Helicobacter pylori shares a coevolutionary history with humans that predates the out-of-Africa diaspora, and the geographical specificities of H. pylori populations reflect multiple well-known human migrations. We extensively sampled H. pylori from 16 ethnically diverse human populations across Siberia to help resolve whether ancient northern Eurasian populations persisted at high latitudes through the last glacial maximum and the relationships between present-day Siberians and Native Americans. A total of 556 strains were cultivated and genotyped by multilocus sequence typing, and 54 representative draft genomes were sequenced. The genetic diversity across Eurasia and the Americas was structured into three populations: hpAsia2, hpEastAsia, and hpNorthAsia. hpNorthAsia is closely related to the subpopulation hspIndigenousAmericas from Native Americans. Siberian bacteria were structured into five other subpopulations, two of which evolved through a divergence from hpAsia2 and hpNorthAsia, while three originated though Holocene admixture. The presence of both anciently diverged and recently admixed strains across Siberia support both Pleistocene persistence and Holocene recolonization. We also show that hspIndigenousAmericas is endemic in human populations across northern Eurasia. The evolutionary history of hspIndigenousAmericas was reconstructed using approximate Bayesian computation, which showed that it colonized the New World in a single migration event associated with a severe demographic bottleneck followed by low levels of recent admixture across the Bering Strait.