Many people alive today possess some Neanderthal ancestry, according to a landmark scientific study.
The finding has surprised many experts, as previous genetic evidence suggested the Neanderthals made little or no contribution to our inheritance.
The result comes from analysis of the Neanderthal genome - the "instruction manual" describing how these ancient humans were put together.
Between 1% and 4% of the Eurasian human genome seems to come from Neanderthals.
But the study confirms living humans overwhelmingly trace their ancestry to a small population of Africans who later spread out across the world.
The most widely-accepted theory of modern human origins - known as Out of Africa - holds that the ancestors of living humans (Homo sapiens) originated in Africa some 200,000 years ago.
A relatively small group of people then left the continent to populate the rest of the world between 50,000 and 60,000 years ago.
While the Neanderthal genetic contribution - found in people from Europe, Asia and Oceania - appears to be small, this figure is higher than previous genetic analyses have suggested.
"They are not totally extinct. In some of us they live on, a little bit," said Professor Svante Paabo, from the Max Planck Institute for Evolutionary Anthropology in Leipzig, Germany.
Professor Chris Stringer, research leader in human origins at London's Natural History Museum, is one of the architects of the Out of Africa theory. He told BBC News: "In some ways [the study] confirms what we already knew, in that the Neanderthals look like a separate line.
"But, of course, the really surprising thing for many of us is the implication that there has been some interbreeding between Neanderthals and modern humans in the past."
John Hawks, assistant professor of anthropology at the University of Wisconsin-Madison in the US, told BBC News: "They're us. We're them.
"It seemed like it was likely to be possible, but I am surprised by the amount. I really was not expecting it to be as high as 4%," he said of the genetic contribution from Neanderthals.
The sequencing of the Neanderthal genome is a landmark scientific achievement, the product of a four-year-long effort led from Germany's Max Planck Institute but involving many other universities around the world.
The project makes use of efficient "high-throughput" technology which allows many genetic sequences to be processed at the same time.
The draft Neanderthal sequence contains DNA extracted from the bones of three different Neanderthals found at Vindija Cave in Croatia.
Retrieving good quality genetic material from remains tens of thousands of years old presented many hurdles which had to be overcome.
The samples almost always contained only a small amount of Neanderthal DNA amid vast quantities of DNA from bacteria and fungi that colonised the remains after death.
The Neanderthal DNA itself had broken down into very short segments and had changed chemically. Luckily, the chemical changes were of a predictable nature, allowing the researchers to write software that corrected for them.
Writing in Science journal, the researchers describe how they compared this draft sequence with the genomes of modern people from around the globe.
"The comparison of these two genetic sequences enables us to find out where our genome differs from that of our closest relative," said Professor Paabo.
The results show that the genomes of non-Africans (from Europe, China and New Guinea) are closer to the Neanderthal sequence than are those from Africa.
The most likely explanation, say the researchers, is that there was limited mating, or "gene flow", between Neanderthals and the ancestors of present-day Eurasians.
This must have taken place just as people were leaving Africa, while they were still part of one pioneering population. This mixing could have taken place either in North Africa, the Levant or the Arabian Peninsula, say the researchers.
Professor Stringer added: "Any functional significance of these shared genes remains to be determined, but that will certainly be a focus for the next stages of this fascinating research."
The Out of Africa theory contends that modern humans replaced local "archaic" populations like the Neanderthals.
But there are several variations on this idea. The most conservative model proposes that this replacement took place with no interbreeding between modern humans and Neanderthals.
Another version allows for a degree of assimilation, or absorption, of other human types into the Homo sapiens gene pool.
The latest research strongly supports the Out of Africa theory, but it falsifies the most conservative version of events.
The team identified more than 70 gene changes that were unique to modern humans. These genes are implicated in physiology, the development of the brain, skin and bone.
The researchers also looked for signs of "selective sweeps" - strong natural selection acting to boost traits in modern humans. They found 212 regions where positive selection may have been taking place.
The scientists are interested in discovering genes that distinguish modern humans from Neanderthals because they may have given our evolutionary line certain advantages over the course of evolution.
The most obvious differences were in physique: the muscular, stocky frames of Neanderthals contrast sharply with those of our ancestors. But it is likely there were also more subtle differences, in behaviour, for example.
Dr Hawks commented that the amount of Neanderthal DNA in our genomes seemed high: "What it means is that any traits [Neanderthals] had that might have been useful in later populations should still be here.
"So when we see that their anatomies are gone, this isn't just chance. Those things that made the Neanderthals apparent to us as a population - those things didn't work. They're gone because they didn't work in the context of our population."
Researchers had previously thought Europe was the region where Neanderthals and modern humans were most likely to have exchanged genes. The two human types overlapped here for some 10,000 years.
The authors of the paper in Science do not rule out some interbreeding in Europe, but say it was not possible to detect this with present scientific methods.