Southwestern Angola is a region characterized by contact between indigenous foragers and incoming food-producers, involving genetic and cultural exchanges between peoples speaking Kx'a, Khoe-Kwadi, and Bantu languages. Although present-day Bantu speakers share a patrilocal residence pattern and matrilineal principle of clan and group membership, a highly stratified social setting divides dominant pastoralists from marginalized groups that subsist on alternative strategies and have previously been thought to have pre-Bantu origins. Here, we compare new high-resolution sequence data from 2.3 Mb of the male-specific region of the Y chromosome (MSY) from 170 individuals with previously reported mitochondrial DNA (mtDNA) genomes, to investigate the population history of seven representative southwestern Angolan groups (Himba, Kuvale, Kwisi, Kwepe, Twa, Tjimba, !Xun), and to study the causes and consequences of sex-biased processes in their genetic variation. We found no clear link between the formerly Kwadi-speaking Kwepe and pre-Bantu eastern African migrants, and no pre-Bantu MSY lineages among Bantu-speaking groups, except for small amounts of "Khoisan" introgression. We therefore propose that irrespective of their subsistence strategies, all Bantu-speaking groups of the area share a male Bantu origin. Additionally, we show that in Bantu-speaking groups, the levels of among-group and between-group variation are higher for mtDNA than for MSY. These results, together with our previous demonstration that the matriclanic systems of southwestern Angolan Bantu groups are genealogically consistent, suggest that matrilineality strongly enhances both female population sizes and interpopulation mtDNA variation.