The ability to digest milk into adulthood, lactase persistence (LP), as well as specific genetic variants associated with LP, is heterogeneously distributed in global populations. These variants were most likely targets of selection when some populations converted from hunter-gatherer to pastoralist or farming lifestyles. Specific LP polymorphisms are associated with particular geographic regions and populations; however, they have not been extensively studied in southern Africa. We investigate the LP-regulatory region in 267 individuals from 13 southern African populations (including descendants of hunter-gatherers, pastoralists, and agropastoralists), providing the first comprehensive study of the LP-regulatory region in a large group of southern Africans. The “East African” LP single-nucleotide polymorphism (SNP) (14010G>C) was found at high frequency (>20%) in a strict pastoralist Khoe population, the Nama of Namibia, suggesting a connection to East Africa, whereas the “European” LP SNP (13910C>T) was found in populations of mixed ancestry. Using genome-wide data from various African populations, we identify admixture (13%) in the Nama, from an Afro-Asiatic group dating to >1,300 years ago, with the remaining fraction of their genomes being from San hunter-gatherers. We also find evidence of selection around the LCT gene among Khoe-speaking groups, and the substantial frequency of the 14010C variant among the Nama is best explained by adaptation to digesting milk. These genome-local and genome-wide results support a model in which an East African group brought pastoralist practices to southern Africa and admixed with local hunter-gatherers to form the ancestors of Khoe people.