How and when did humans colonise the globe? This question has become one of the key concerns of archaeologists, geneticists and human biologists. And now the latest archaeological discovery in Oman in the Arabian Peninsula – distinctive Nubian stone tools – offers a new twist in the emerging story.

In the 19th century, Charles Darwin speculated that all humans, Homo sapiens, had a common ancestor who had lived in Africa, implying that at some point in the past humans must have spread from Africa to other land masses around the world.

But modern studies of this process were reinvigorated by genetic evidence that clearly showed that the far greater genetic diversity of humans outside Africa reflects their dispersal from a common origin in Africa.

Since that realisation, geneticists have estimated the likely antiquity of human migration out of Africa, and their analyses generally suggest humans emerged only 50,000 and 70,000 years ago.

Archaeologists have also been searching for the traces left behind by the great initial migrations of humans. This has often proved difficult, because humans were not the first hominids to leave Africa. Earlier migrations by Homo erectus, Homo heidelbergensis and others had already occurred, and these hominids had spread across the Old World, giving rise to Neanderthals in Europe, Denisovans in central Asia and the “Hobbit” (Homo floresiensis) in island Southeast Asia.

These hominids also left behind tools of stone and bones from meals and it has sometimes been hard for archaeologists to determine whether archaeological materials were created by modern humans or by earlier hominids.

For this reason, archaeological research in lands not colonised by earlier hominids provides an ideal situation for recognising the dispersal of humans. In those landscapes, we know the oldest dated archaeological objects represent the age of human migrations.

Humans travelling southeast from southern Asia arrived in the Philippines about 65,000 years ago, and they reached Australia 55,000 years ago. But when did they leave Africa?

The most recent archaeological discoveries in Oman suggest humans may have left Africa early. Writing in the technical journal PLoS One , a team lead by Jeffrey I Rose of Birmingham University has described finding sites near the southern coastline of the Arabian Peninsula. These sites contain stone artefacts called Levallois cores, which are distinctive of a manufacturing system named the “Nubian complex” known from the Sudan in northeastern Africa.

Rose and his colleagues think this is evidence of the movement of people from Africa, across the narrow Bab-el-Mandeb straits of the Red Sea and into the Arabian Peninsula. Perhaps this could have been the start of the long migration eastward, as humans colonised the coast of south Asia, then spreading to Southeastern Asia, and eventually Australia.

Rose and his team focused on the open-air site of Aybut Al Auwal, where an ancient campsite was positioned on a relic river terrace. Excavations there yielded samples that were dated to between 100,000 and 113,000 years old. This date is controversial because it is far older than the estimates for human emergence from Africa provided by genetic studies of modern humans.

How do we explain the apparent conflict between archaeological and genetic studies? Perhaps we have hard evidence that something is wrong with the genetic estimates for the age of the common ancestor of non-African humans.

If that were the case, Rose may have found the first footsteps of humans on their journey to Australia. But the humans creating his sites need not have survived to become the ancestors of modern humans. It is more likely that these sites represent a failure.

This might well be debris from a group who left Africa but who subsequently died out. Later groups of human migrants may have moved out of Africa and eventually colonised the globe.

The new evidence from Oman points to a complex story. The emergence of humans from Africa was not a simple triumphal march around the world: it was a long process of exploration and expansion, of risk and achievement.

It seems our ancestors had an evolutionary and demographic history containing failures as well as successes. The unfolding story of our origins is full of drama and is witness to loss and disappointment as much as of accomplishment.

Our colonisation of this planet truly was a long, hard journey.