We assembled genome-wide data from 16 prehis- toric 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 approximately two-thirds of the ancestry of Malawi hunter-gatherers $8,100– 2,500 years ago and approximately one-third of the ancestry of Tanzanian hunter-gatherers $1,400 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 $3,100-year-old pastoralist from Tanzania contributed ancestry to people from north- eastern to southern Africa, including a $1,200-year- old southern African pastoralist. The deepest diversi- fications of African lineages were complex, involving either repeated gene flow among geographically disparate groups or a lineage more deeply diverging than that of the San contributing more to some west- ern African populations than to others. We finally leverage ancient genomes to document episodes of natural selection in southern African populations.