The extent to which past climate change has dictated the pattern and timing of the out-of-Africa expansion by anatomically modern humans is currently unclear [Stewart JR, Stringer CB (2012) Science 335:1317-1321]. In particular, the incompleteness of the fossil record makes it difficult to quantify the effect of climate. Here, we take a different approach to this problem; rather than relying on the appearance of fossils or archaeological evidence to determine arrival times in different parts of the world, we use patterns of genetic variation in modern human populations to determine the plausibility of past demographic parameters. We develop a spatially explicit model of the expansion of anatomically modern humans and use climate reconstructions over the past 120 ky based on the Hadley Centre global climate model HadCM3 to quantify the possible effects of climate on human demography. The combinations of demographic parameters compatible with the current genetic makeup of worldwide populations indicate a clear effect of climate on past population densities. Our estimates of this effect, based on population genetics, capture the observed relationship between current climate and population density in modern hunter-gatherers worldwide, providing supporting evidence for the realism of our approach. Furthermore, although we did not use any archaeological and anthropological data to inform the model, the arrival times in different continents predicted by our model are also broadly consistent with the fossil and archaeological records. Our framework provides the most accurate spatiotemporal reconstruction of human demographic history available at present and will allow for a greater integration of genetic and archaeological evidence.