Phylogeographic patterns in wide-ranging species in southern Africa remain largely unexplored, especially in areas north of South Africa. Here, we investigate population structuring, demographic history, and the colonization pattern of the western rock skink (Trachylepis sulcata), a rock-dwelling species with a range extending from southwestern South Africa into Angola. Using 1056 bp from the mitochondrial marker ND2 and > 2.5 kb from three nuclear genes (EXPH5, KIF24, RAG-1), we constructed allele networks, generated extended Bayesian skyline plots and performed population clustering analyses. Analyses of historical demographic patterns show an overall southward range expansion from Northern Namibia into Southern Namibia and South Africa, although we find contrasting genetic breaks across these geographic regions using nuclear and mitochondrial data. We suggest that mtDNA has introgressed across a nuclear break corresponding to the Knersvlakte region of South Africa, a previously proposed biogeographic barrier for rupicolous species. This pattern of mitochondrial variation contrasts sharply to that of other South African taxa previously investigated, which all show significant mtDNA differentiation across the Knersvlakte region. Additionally, while other taxa show divergences dating to the Pliocene, T. sulcata appears to be a recent arrival in southern Africa, having crossed this barrier and colonized South Africa in the mid-Pleistocene. The complex phylogeographic history of T. sulcata corroborates the intricate patterns of genetic variation found in South African taxa and provides novel insight into historical processes affecting species distributed across Namibia. Keywords: Phylogeography, population genetics-empirical, reptiles, speciation.