Tool making hominid species left their African homeland several times in the past, the earliest being shortly after the appearance of Homo erectus, about 1.8 Ma ago.  Those early migrants ended up in eastern Asia, where they thrived until as recently as 12 thousand years ago (if indeed H. floresiensis does prove to be a miniature erect).  Europe was reached by at least three waves: possibly advanced H. erectus around 0.5 Ma; Neanderthals as early as 0.25 Ma; modern humans around 40 thousand years ago, at the earliest.  The fully modern human record in Asia begins at 67 thousand years ago, suggesting an exodus from Africa at between 80 and 70 thousand years.  There is an oddity here: simple geography suggests that Europe should have been colonised first in each wave out of Africa, because it is closer.  But the Nile to Middle East to Europe route was not successfully used by our immediate forebears until long after they moved eastwards, although there is evidence of H. sapiens temporary occupation of parts of Palestine between 100 to 80 thousand years.  Several reasons for this have been suggested, including the possibility of direct competition with Neanderthals who occupied the same 100 ka sites in the Middle East, and the relative difficulty of passage along the Nile compared with a coastal route in NE Africa. 

Eritrean and US archaeologists have shown that around 100 ka the Eritrean coast was occupied by humans who subsisted on seafood: always available whatever the climate, whereas terrestrial game potential fluctuates.  That has led to the suggestion that Africans who colonised Asia and Australasia left by island hopping across the narrow Straits of Bab el Mandab when sea-level began to fall around 70 ka.  A coastal route, well stocked with food items would have allowed rapid movement eastwards.  That seems intuitively likely, because an eastward route through the Middle East is barred by deserts, which would have been even more arid as glacial conditions developed.  Moreover, a Middle Eastern route would have led more directly to Asia Minor and ultimately Europe.  The conundrum deepens, since the Straits of Bab el Mandab would have been even easier to cross at the time of the last glacial maximum, around 20 ka, yet there are no archaeological signs of populations of that age in Yemen and Oman; research has hardly begun there.  Unravelling routes is possible, just, by analysing modern population genetics (Macaulay, V. et al. 2005. Single, rapid coastal settlement of Asia by analysis of complete mitochondrial genomes.  Science, v. 308, p. 1034-1036).  People living in the Andaman islands and the Malaysian Peninsula include groups who differ substantially from their neighbours and may be descendants of the original colonisers.  Mitochondrial DNA from these groups indicates a branching from an original type around 65 ka, remarkably suggesting a single founding woman.  That cannot be taken exactly at face value, but does suggest that only a small band migrated to these two areas, perhaps no larger than a few hundred.  The fact that they reached the Andaman islands may indicate that theirs was a boat-using culture.  Whatever, movement was rapid, possibly as high as 4 km per year, thereby allowing the early colonisation of Australia.

Analyses of mtDNA in Africa suggest that about 85 ka ago there was a major expansion of people, whose descendants make up more than two thirds of modern Africans.  Could it be that this expansion reflected climate and ecological change, so that migration from elsewhere drove inhabitants of the Red Sea coast to cross the daunting Straits of Bab el Mandab because of severe competition?  Perhaps it was the driving force as late as 40 ka, when modern humans reached Europe itself, undoubtedly along the Middle East route.

See also:  Forster, P. & Matsumura, S. 2005.  Did early humans go north or south?  Science, v. 3308, p. 965-966.