Both the Levantine Corridor and the Horn of Africa route have figured prominently in early hominid migrations from Africa to Eurasia. To gauge the importance of these two African-Asian thoroughfares in the demic movements of modern man, we surveyed the mtDNA control region variation and coding polymorphisms of 739 individuals representing ten African and Middle Eastern populations. Two of these collections, Egypt and Yemen, are geographically close to the Levant and Horn of Africa, respectively. In this analysis, we uncover genetic evidence for the preferential use of the Levantine Corridor in the Upper Paleolithic to Neolithic dispersals of haplogroups H, J*, N1b, and T1, in contrast to an overwhelming preference in favor of the Horn of Africa for the intercontinental expansion of M1 during the Middle to Upper Paleolithic. Furthermore, we also observed a higher frequency of sub-Saharan mtDNA compared to NRY lineages in the Middle Eastern collections, a pattern also seen in previous studies. In short, the results of this study suggest that several migratory episodes of maternal lineages occurred across the African-Asian corridors since the first African exodus of modern Homo sapiens sapiens.