A major unanswered question regarding the dispersal of modern humans around the world concerns the geographical site of the first human steps outside of Africa. The "southern coastal route" model predicts that the early stages of the dispersal took place when people crossed the Red Sea to southern Arabia, but genetic evidence has hitherto been tenuous. We have addressed this question by analyzing the three minor west-Eurasian haplogroups, N1, N2, and X. These lineages branch directly from the first non-African founder node, the root of haplogroup N, and coalesce to the time of the first successful movement of modern humans out of Africa, ∼60 thousand years (ka) ago. We sequenced complete mtDNA genomes from 85 Southwest Asian samples carrying these haplogroups and compared them with a database of 300 European examples. The results show that these minor haplogroups have a relict distribution that suggests an ancient ancestry within the Arabian Peninsula, and they most likely spread from the Gulf Oasis region toward the Near East and Europe during the pluvial period 55-24 ka ago. This pattern suggests that Arabia was indeed the first staging post in the spread of modern humans around the world.