The emergence of more refined chronologies for climate change and archaeology in prehistoric Africa, and for the evolution of human mitochondrial DNA (mtDNA), now make it feasible to test more sophisticated models of early modern human dispersals suggested by mtDNA distributions. Here we have generated 42 novel whole-mtDNA genomes belonging to haplogroup LO, the most divergent clade in the maternal line of descent, and analysed them alongside the growing database of African lineages belonging to L0's sister clade, L1'6. We propose that the last common ancestor of modern human mtDNAs (carried by "mitochondrial Eve") possibly arose in central Africa ∼180 ka, at a time of low population size. By ∼130 ka two distinct groups of anatomically modern humans co-existed in Africa: broadly, the ancestors of many modern-day Khoe and San populations in the south and a second central/eastern African group that includes the ancestors of most extant worldwide populations. Early modern human dispersals correlate with climate changes, particularly the tropical African "megadroughts" of MIS 5 (marine isotope stage 5, 135-75 ka) which paradoxically may have facilitated expansions in central and eastern Africa, ultimately triggering the dispersal out of Africa of people carrying haplogroup L3 ∼60 ka. Two south to east migrations are discernible within haplogroup LO. One, between 120 and 75 ka, represents the first unambiguous long-range modern human dispersal detected by mtDNA and might have allowed the dispersal of several markers of modernity. A second one, within the last 20 ka signalled by L0d, may have been responsible for the spread of southern click-consonant languages to eastern Africa, contrary to the view that these eastern examples constitute relicts of an ancient, much wider distribution.