Africa was the birth-place of Homo sapiens and has the earliest evidence for symbolic behaviour and complex technologies. The best-attested early flowering of these distinctive features was in a glacial refuge zone on the southern coast 100-70 ka, with fewer indications in eastern Africa until after 70 ka. Yet it was eastern Africa, not the south, that witnessed the first major demographic expansion, ~70-60 ka, which led to the peopling of the rest of the world. One possible explanation is that important cultural traits were transmitted from south to east at this time. Here we identify a mitochondrial signal of such a dispersal soon after ~70 ka - the only time in the last 200,000 years that humid climate conditions encompassed southern and tropical Africa. This dispersal immediately preceded the out-of-Africa expansions, potentially providing the trigger for these expansions by transmitting significant cultural elements from the southern African refuge.