It has been shown that Neanderthals contributed genetically to modern humans outside Africa 47,000-65,000 years ago. Here we analyse the genomes of a Neanderthal and a Denisovan from the Altai Mountains in Siberia together with the sequences of chromosome 21 of two Neanderthals from Spain and Croatia. We find that a population that diverged early from other modern humans in Africa contributed genetically to the ancestors of Neanderthals from the Altai Mountains roughly 100,000 years ago. By contrast, we do not detect such a genetic contribution in the Denisovan or the two European Neanderthals. We conclude that in addition to later interbreeding events, the ancestors of Neanderthals from the Altai Mountains and early modern humans met and interbred, possibly in the Near East, many thousands of years earlier than previously thought.

M.J.H. was supported by the National Science Foundation Graduate Research Fellowship under grant DGE-1144153. T.M-B. was supported by ICREA, EMBO YIP 2013 and Fundació Barcelona Zoo. The Max Planck Society, the Krekeler Foundation, MINECO (grants BFU2014-55090-P FEDER, BFU2015-7116-ERC and BFU2015-6215-ERC to T.M-B. and BFU2012-34157 FEDER to C.L.-F.) and the US National Institutes of Health (grant GM102192 to A.S. and U01 MH106874 to T.M-B.) provided financial support