We assembled genome-wide data from 16 prehistoric Africans. We show that the anciently divergent lineage that comprises the primary ancestry of the southern African San had a wider distribution in the past, contributing ~2/3 of the ancestry of Malawi hunter-gatherers ~8100-2500 years ago, and ~1/3 of Tanzanian hunter-gatherers ~1400 years ago. We document how the spread of farmers from western Africa involved complete replacement of local hunter-gatherers in some regions, and we track the spread of herders by showing that the population of a ~3100 year-old pastoralist from Tanzania contributed ancestry to people from northeast to southern Africa, including a ~1200-year-old southern African pastoralist. The deepest diversifications of African lineages were complex, involving long-distance gene flow, or a lineage more deeply diverging than that of the San contributing more to some western Africans than others. We finally leverage ancient genomes to document episodes of natural selection in southern African populations.