Neanderthals and modern humans were interbreeding much earlier than was previously thought, scientists say.
Traces of human DNA found in a Neanderthal genome suggest that we started mixing with our now-extinct relatives 100,000 years ago.
Previously it had been thought that the two species first encountered each other when modern humans left Africa, about 60,000 years ago.
The research is published in the journal 'Nature'.
Dr Sergi Castellano, from the Max Planck Institute for Evolutionary Anthropology, in Germany, has told BBC: "It is significant for understanding the history of modern humans and Neanderthals."
The ancient remains of a female Neanderthal, found in a remote cave in the Altai Mountains in Siberia, are the source of these revelations about the sex lives of our ancestors.
A genetic analysis reveals that portions of human DNA lie within her genome, revealing an interspecies mingling that took place 100,000 years ago.
Earlier research suggested that humans started interbreeding with our heavy-browed, stocky relatives when they migrated out of Africa and began to spread around the world.
As they left the continent, they met and mingled with the Neanderthals, who lived across Europe and Asia.
Neanderthal genes from these encounters are found in humans today, and recent studies have shown that these portions of DNA play an integral role in everything from our immune system to our propensity to diseases.
But the latest finding of a flow of genes in the opposite direction, from humans to Neanderthals, suggests such mating was happening thousands of years earlier.
It is not yet clear what impact these genes had on Neanderthals.
If early humans were having sex with Neanderthals 100,000 years ago, then they must have been doing so outside of Africa because our close relatives were not found there.
And this means that they had left Africa before the larger dispersal that took place at least 40,000 years later.
This adds to the idea that early forays out of the continent took place. Other recent evidence includes early human fossils found in Skhul and Qafzeh in Israel, and recent research that suggests people were living in China at least 80,000 years ago.
Commenting on the study Prof Chris Stringer, research leader in human origins, from the Natural History Museum in London, notes that geneticists should be able to eventually show if the transfer of DNA in either direction was mainly via males, females, or about equal in proportion, but it will need a lot more data before that becomes possible."