We have analyzed and compared mitochondrial DNA variation of populations from the Near East and Africa and found a very high frequency of African lineages present in the Yemen Hadramawt: more than a third were of clear sub-Saharan origin. Other Arab populations carried ∼10% lineages of sub-Saharan origin, whereas non-Arab Near Eastern populations, by contrast, carried few or no such lineages, suggesting that gene flow has been preferentially into Arab populations. Several lines of evidence suggest that most of this gene flow probably occurred within the past ∼2,500 years. In contrast, there is little evidence for male-mediated gene flow from sub-Saharan Africa in Y-chromosome haplotypes in Arab populations, including the Hadramawt. Taken together, these results are consistent with substantial migration from eastern Africa into Arabia, at least in part as a result of the Arab slave trade, and mainly female assimilation into the Arabian population as a result of miscegenation and manumission.