Grey wolves (Canis lupus) are one of the few large terrestrial carnivores that have maintained a wide geographical distribution across the Northern Hemisphere throughout the Pleistocene and Holocene. Recent genetic studies have suggested that, despite this continuous presence, major demographic changes occurred in wolf populations between the Late Pleistocene and early Holocene, and that extant wolves trace their ancestry to a single Late Pleistocene population. Both the geographical origin of this ancestral population and how it became widespread remain unknown. Here, we used a spatially and temporally explicit modelling framework to analyse a data set of 90 modern and 45 ancient mitochondrial wolf genomes from across the Northern Hemisphere, spanning the last 50,000 years. Our results suggest that contemporary wolf populations trace their ancestry to an expansion from Beringia at the end of the Last Glacial Maximum, and that this process was most likely driven by Late Pleistocene ecological fluctuations that occurred across the Northern Hemisphere. This study provides direct ancient genetic evidence that long-range migration has played an important role in the population history of a large carnivore, and provides insight into how wolves survived the wave of megafaunal extinctions at the end of the last glaciation. Moreover, because Late Pleistocene grey wolves were the likely source from which all modern dogs trace their origins, the demographic history described in this study has fundamental implications for understanding the geographical origin of the dog.