Rare mitochondrial lineages with relict distributions can sometimes be disproportionately informative about deep events in human prehistory. We have studied one such lineage, haplogroup R0a, which uniquely is most frequent in Arabia and the Horn of Africa, but is distributed much more widely, from Europe to India. We conclude that: (1) the lineage ancestral to R0a is more ancient than previously thought, with a relict distribution across the Mediterranean/Southwest Asia; (2) R0a has a much deeper presence in Arabia than previously thought, highlighting the role of at least one Pleistocene glacial refugium, perhaps on the Red Sea plains; (3) the main episode of dispersal into Eastern Africa, at least concerning maternal lineages, was at the end of the Late Glacial, due to major expansions from one or more refugia in Arabia; (4) there was likely a minor Late Glacial/early postglacial dispersal from Arabia through the Levant and into Europe, possibly alongside other lineages from a Levantine refugium; and (5) the presence of R0a in Southwest Arabia in the Holocene at the nexus of a trading network that developed after ~3 ka between Africa and the Indian Ocean led to some gene flow even further afield, into Iran, Pakistan and India.