This is the accepted manuscript. The final version is available from Science at http://www.sciencemag.org/content/346/6213/1113.short. ; The origin of contemporary Europeans remains contentious. We obtain a genome sequence from Kostenki 14 in European Russia dating to 38,700-36,200 years ago, one of the oldest fossils of Anatomically Modern Humans from Europe. We find that K14 shares a close ancestry with the 24,000 year old Mal?ta boy from central Siberia, European Mesolithic hunter-gatherers, some contemporary western Siberians and many Europeans, but not eastern Asians. Additionally, the Kostenki 14 genome shows evidence of shared ancestry with a population basal to all Eurasians that also relates to later European Neolithic farmers. We find that Kostenki 14 contains more Neandertal DNA that is contained in longer tracts than present Europeans. Our findings reveal the timing of divergence of western Eurasians and East Asians to be >36,200 years ago, and that European genomic structure today dates back to the Upper Paleolithic and derives from a meta-population that at times stretched from Europe to central Asia. ; GeoGenetics members were supported by the Lundbeck Foundation and the Danish National Research Foundation (DNRF94). ASM was supported by the Swiss National Science Foundation (PBSKP3_143529). Research on the archaeological background by PRN was supported by a MC Career Integration Grant (322261).