Ancient DNA analyses have provided enhanced resolution of population histories in many Pleistocene taxa. However, most studies are spatially restricted, making inference of species-level biogeographic histories difficult. Here, we analyse mitochondrial DNA (mtDNA) variation in the woolly mammoth from across its Holarctic range to reconstruct its history over the last 200 thousand years (kyr). We identify a previously undocumented major mtDNA lineage in Europe, which was replaced by another major mtDNA lineage 32–34 kyr before present (BP). Coalescent simulations provide support for demographic expansions at approximately 121 kyr BP, suggesting that the previous interglacial was an important driver for demography and intraspecific genetic divergence. Furthermore, our results suggest an expansion into Eurasia from America around 66 kyr BP, coinciding with the first exposure of the Bering Land Bridge during the Late Pleistocene. Bayesian inference indicates Late Pleistocene demographic stability until 20–15 kyr BP, when a severe population size decline occurred.