Increasing globalization has promoted the spread of exotic species, including disease vectors. Understanding the evolutionary processes involved in such colonizations is both of intrinsic biological interest and important to predict and mitigate future disease risks. The Aedes aegypti mosquito is a major vector of dengue, chikungunya and Zika, the worldwide spread of which has been facilitated by Ae. aegypti’s adaption to human-modified environments. Understanding the evolutionary processes involved in this invasion requires characterization of the genetic make-up of the source population(s). The application of approximate Bayesian computation (ABC) to sequence data from four nuclear and one mitochondrial marker revealed that African populations of Ae. aegypti best fit a demographic model of lineage diversification, historical admixture and recent population structuring. As ancestral Ae. aegypti were dependent on forests, this population history is consistent with the effects of forest fragmentation and expansion driven by Pleistocene climatic change. Alternatively, or additionally, historical human movement across the continent may have facilitated their recent spread and mixing. ABC analysis and haplotype networks support earlier inferences of a single out-of-Africa colonization event, while a cline of decreasing genetic diversity indicates that Ae. aegypti moved first from Africa to the Americas and then to Asia. ABC analysis was unable to verify this colonization route, possibly because the genetic signal of admixture obscures the true colonization pathway. By increasing genetic diversity and forming novel allelic combinations, divergence and historical admixture within Africa could have provided the adaptive potential needed for the successful worldwide spread of Ae. aegypti.