Past population size can be estimated from modern genetic diversity using coalescent theory. Estimates of ancestral human population dynamics in sub-Saharan Africa can tell us about the timing and nature of our first steps towards colonizing the globe. Here, we combine Bayesian coalescent inference with a dataset of 224 complete human mitochondrial DNA (mtDNA) sequences to estimate effective population size through time for each of the four major African mtDNA haplogroups (L0-L3). We find evidence of three distinct demographic histories underlying the four haplogroups. Haplogroups L0 and L1 both show slow, steady exponential growth from 156 to 213kyr ago. By contrast, haplogroups L2 and L3 show evidence of substantial growth beginning 12-20 and 61-86kyr ago, respectively. These later expansions may be associated with contemporaneous environmental and/or cultural changes. The timing of the L3 expansion--8-12kyr prior to the emergence of the first non-African mtDNA lineages--together with high L3 diversity in eastern Africa, strongly supports the proposal that the human exodus from Africa and subsequent colonization of the globe was prefaced by a major expansion within Africa, perhaps driven by some form of cultural innovation.