Scientists have redated fossil bones from two sites in Spain and discovered they are much older than previously thought.
According to the new evidence, it is unlikely Neanderthals and modern humans ever lived together in the region.
Researchers now think the Neanderthals had long gone before the arrival of the first Homo sapiens.
Since the 1990s, experts have believed the last Neanderthals sought refuge in the Spanish peninsula and finally died out around 30,000 years ago.
That would have provided easily enough time for the Neanderthals to mix their DNA with that of modern humans, who are believed to have colonised Spain more than 10,000 years earlier.
But the new research, using an improved dating method, indicates that the Neanderthal occupation of Spain only lasted until around 45-50,000 years ago.
Interbreeding has been suggested as the reason why traces of Neanderthal DNA can be found in people today, especially Europeans.
However the issue has divided experts. Some believe the genetic link is due to Neanderthals and modern humans having a common ancestor which may have lived in North Africa.
Neanderthals and modern humans are distantly related. Both are thought to have emigrated to Eurasia from Africa, but at different times.
Scientists tested several animal bones found alongside ancient stone tools and bearing cut marks and other signs of human interference.
Previously, radiocarbon dating had supported the idea that the bones were evidence of late surviving Neanderthals.
Lead researcher Dr Rachel Wood, from Oxford University, said: "Our results cast doubt on a hypothesis that the last place for surviving Neanderthals was in the southern Iberian peninsula.
"Much of the evidence that has supported this idea is based on a series of radiocarbon dates which cluster at around 35,000 years ago. Our results call all of these results into question."