Modern humans arrived in Europe ~45,000 years ago, but little is known about their genetic composition before the start of farming ~8,500 years ago. We analyze genome-wide data from 51 Eurasians from ~45,000-7,000 years ago. 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 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.