Little is currently known about the genetic history of ancient Europeans before the advent of agriculture ~8,500 years ago. Here we have analysed genome-wide data from 51 modern human remains that span around 40,000 years of Eurasian prehistory. Over this time, the proportion of Neanderthal DNA decreased from 3–6% to around 2%, consistent with natural selection against Neanderthal variants in modern humans. Whereas the earliest modern humans in Europe did not contribute substantially to present-day Europeans, all individuals between ~37,000 and ~14,000 years ago descended from a single founder population which forms part of the ancestry of present-day Europeans. A ~35,000-year-old individual from northwest Europe represents an early branch of this founder population which was then displaced across a broad region, before reappearing in southwest Europe during the last ice age ~19,000 years ago. During the major warming period after ~14,000 years ago, a new genetic component related to present-day Near Easterners appears in Europe. These results document how population turnover and migration have been recurring themes of European pre-history.