Approximately 10 miles separate the Horn of Africa from the Arabian Peninsula at Bab-el-Mandeb (the Gate of Tears). Both historic and archaeological evidence indicate tight cultural connections, over millennia, between these two regions. High-resolution phylogenetic analysis of 270 Ethiopian and 115 Yemeni mitochondrial DNAs was performed in a worldwide context, to explore gene flow across the Red and Arabian Seas. Nine distinct subclades, including three newly defined ones, were found to characterize entirely the variation of Ethiopian and Yemeni L3 lineages. Both Ethiopians and Yemenis contain an almost-equal proportion of Eurasian-specific M and N and African-specific lineages and therefore cluster together in a multidimensional scaling plot between Near Eastern and sub-Saharan African populations. Phylogeographic identification of potential founder haplotypes revealed that approximately one-half of haplogroup L0-L5 lineages in Yemenis have close or matching counterparts in southeastern Africans, compared with a minor share in Ethiopians. Newly defined clade L6, the most frequent haplogroup in Yemenis, showed no close matches among 3,000 African samples. These results highlight the complexity of Ethiopian and Yemeni genetic heritage and are consistent with the introduction of maternal lineages into the South Arabian gene pool from different source populations of East Africa. A high proportion of Ethiopian lineages, significantly more abundant in the northeast of that country, trace their western Eurasian origin in haplogroup N through assorted gene flow at different times and involving different source populations.