How modern humans dispersed into Eurasia and Australasia, including the number of separate expansions and their timings, is highly debated [1, 2]. Two categories of models are proposed for the dispersal of non-Africans: (1) single dispersal, i.e., a single major diffusion of modern humans across Eurasia and Australasia [3-5]; and (2) multiple dispersal, i.e., additional earlier population expansions that may have contributed to the genetic diversity of some present-day humans outside of Africa [6-9]. Many variants of these models focus largely on Asia and Australasia, neglecting human dispersal into Europe, thus explaining only a subset of the entire colonization process outside of Africa [3-5, 8, 9]. The genetic diversity of the first modern humans who spread into Europe during the Late Pleistocene and the impact of subsequent climatic events on their demography are largely unknown. Here we analyze 55 complete human mitochondrial genomes (mtDNAs) of hunter-gatherers spanning ∼35,000 years of European prehistory. We unexpectedly find mtDNA lineage M in individuals prior to the Last Glacial Maximum (LGM). This lineage is absent in contemporary Europeans, although it is found at high frequency in modern Asians, Australasians, and Native Americans. Dating the most recent common ancestor of each of the modern non-African mtDNA clades reveals their single, late, and rapid dispersal less than 55,000 years ago. Demographic modeling not only indicates an LGM genetic bottleneck, but also provides surprising evidence of a major population turnover in Europe around 14,500 years ago during the Late Glacial, a period of climatic instability at the end of the Pleistocene.