Whilst an African origin of modern humans is well established, the timings and routes of their expansions into Eurasia are the subject of heated debate, due to the scarcity of fossils and the lack of suitably old ancient DNA. Here, we use high-resolution palaeoclimate reconstructions to estimate how difficult it would have been for humans in terms of rainfall availability to leave the African continent in the past 300k years. We then combine these results with an anthropologically and ecologically motivated estimate of the minimum level of rainfall required by hunter-gatherers to survive, allowing us to reconstruct when, and along which geographic paths, expansions out of Africa would have been climatically feasible. The estimated timings and routes of potential contact with Eurasia are compatible with archaeological and genetic evidence of human expansions out of Africa, highlighting the key role of palaeoclimate variability for modern human dispersals.