Scientists say they have evidence that modern humans emerged from Africa up to 50,000 years earlier than currently thought.
The evidence is based on tools found at the Jebel Faya archaeological site in the United Arab Emirates, that they say were made about 125,000 years ago.
The researchers say in the journal Science that they hope their findings will stimulate a re-evaluation of human evolution.
They say the people who made the tools were newcomers in the area with origins on the other side of the Red Sea.
They may have reached the Arabian Peninsula at a time when changes in the climate were transforming it from arid desert into a grassland habitat with lakes and rivers.
These human groups could later have moved on towards the Persian Gulf, trekking around the Iranian coast and on to South Asia.
The researchers were able to date the tools using a light-based technique, which tells scientists when the stone artefacts were buried.
The BBC reports the genetic data strongly points to an exodus from Africa 60,000-70,000 years ago.
The scientists argue that the people who made tools at Jebel Faya 125,000 years ago are ancestral to humans living outside Africa today.
Professor Hans-Peter Uerpmann, from the University of Tuebingen, Germany, said the estimates of time using genetic data were very rough.