Although fossil remains show that anatomically modern humans dispersed out of Africa into the Near East ∼100 to 130 ka, genetic evidence from extant populations has suggested that non-Africans descend primarily from a single successful later migration. Within the human mitochondrial DNA (mtDNA) tree, haplogroup L3 encompasses not only many sub-Saharan Africans but also all ancient non-African lineages, and its age therefore provides an upper bound for the dispersal out of Africa. An analysis of 369 complete African L3 sequences places this maximum at ∼70 ka, virtually ruling out a successful exit before 74 ka, the date of the Toba volcanic supereruption in Sumatra. The similarity of the age of L3 to its two non-African daughter haplogroups, M and N, suggests that the same process was likely responsible for both the L3 expansion in Eastern Africa and the dispersal of a small group of modern humans out of Africa to settle the rest of the world. The timing of the expansion of L3 suggests a link to improved climatic conditions after ∼70 ka in Eastern and Central Africa rather than to symbolically mediated behavior, which evidently arose considerably earlier. The L3 mtDNA pool within Africa suggests a migration from Eastern Africa to Central Africa ∼60 to 35 ka and major migrations in the immediate postglacial again linked to climate. The largest population size increase seen in the L3 data is 3-4 ka in Central Africa, corresponding to Bantu expansions, leading diverse L3 lineages to spread into Eastern and Southern Africa in the last 3-2 ka.