Archaeological studies have revealed cultural connections between the two sides of the Red Sea dating to prehistory. The issue has still not been properly addressed, however, by archaeogenetics. We focus our attention here on the mitochondrial haplogroup HV1 that is present in both the Arabian Peninsula and East Africa. The internal variation of 38 complete mitochondrial DNA sequences (20 of them presented here for the first time) affiliated into this haplogroup testify to its emergence during the late glacial maximum, most probably in the Near East, with subsequent dispersion via population expansions when climatic conditions improved. Detailed phylogeography of HV1 sequences shows that more recent demographic upheavals likely contributed to their spread from West Arabia to East Africa, a finding concordant with archaeological records suggesting intensive maritime trade in the Red Sea from the sixth millennium BC onwards. Closer genetic exchanges are apparent between the Horn of Africa and Yemen, while Egyptian HV1 haplotypes seem to be more similar to the Near Eastern ones.