We investigated the genetic history of southern African populations with a special focus on their paternal history. We reexamined previous claims that the Y-chromosome haplogroup E1b1b (E-M293) was brought to southern Africa by pastoralists from eastern Africa, and investigated patterns of sex-biased gene flow in southern Africa.We analyzed previously published complete mtDNA genome sequences and ∼900 kb of NRY sequences from 23 populations from Namibia, Botswana, and Zambia, as well as haplogroup frequencies from a large sample of southern African populations and 23 newly genotyped Y-linked STR loci for samples assigned to haplogroup E1b1b.Our results support an eastern African origin for Y-chromosome haplogroup E1b1b (E-M293); however, its current distribution in southern Africa is not strongly associated with pastoralism, suggesting more complex demographic events and/or changes in subsistence practices in this region. The Bantu expansion in southern Africa had a notable genetic impact and was probably a rapid, male-dominated expansion. Our finding of a significant increase in the intensity of the sex-biased gene flow from north to south may reflect changes in the social dynamics between Khoisan and Bantu groups over time.Our study shows that the population history of southern Africa has been complex, with different immigrating groups mixing to different degrees with the autochthonous populations. The Bantu expansion led to heavily sex-biased admixture as a result of interactions between Khoisan females and Bantu males, with a geographic gradient which may reflect changes in the social dynamics between Khoisan and Bantu groups over time.