Climatic change is widely acknowledged to have played a role in the dispersal of modern humans out of Africa, but the timing is contentious. Genetic evidence links dispersal to climatic change ~60,000 years ago, despite increasing evidence for earlier modern human presence in Asia. We report a deep seismic and near-continuous core record of the last 150,000 years from Lake Tana, Ethiopia, close to early modern human fossil sites and to postulated dispersal routes. The record shows varied climate towards the end of the penultimate glacial, followed by an abrupt change to relatively stable moist climate during the last interglacial. These conditions could have favoured selection for behavioural versatility, population growth and range expansion, supporting models of early, multiple dispersals of modern humans from Africa.