A systematic study of the Trachylepis varia complex was conducted using mitochondrial and nuclear DNA markers for individuals sampled across the species range. The taxonomic history of T. varia has been complicated and its broad geographic distribution and considerable phenotypic variation has made taxonomic revision difficult, leading earlier taxonomists to suggest that T. varia is a species complex. We used maximum likelihood and Bayesian inference to estimate gene trees and a multilocus time-tree, respectively, and we used these trees to identify the major clades (putative species) within T. varia. Additionally, we used morphological and color pattern data to distinguish and revise the taxonomy of the southern African clades. The major clades recovered in the multilocus time-tree were recovered in each of gene trees, although the relationships among these major clades differed across gene trees. Genetic data support the existence of at least eight species within the T. varia complex, each of which originated during the mid to late Miocene or early Pliocene. We focus our systematic discussion on the southern African members of the T. varia complex, revive Trachylepis damarana (Peters, 1870) and T. laevigata (Peters, 1869), and designate lectotypes for T. damarana and T. varia.