The diversity of lacertid lizards in Africa is highest in the southern African subcontinent, where over two-thirds of the species are endemic. With eleven currently recognized species, Pedioplanis is the most diverse among the southern African genera. In this study we use 2200 nucleotide positions derived from two mitochondrial markers (ND2 and 16S rRNA) and one nuclear gene (RAG-1) to (i) assess the phylogeny of Pedioplanis and (ii) estimate divergence time among lineages using the relaxed molecular clock method. Individual analyses of each gene separately supported different nodes in the phylogeny and the combined analysis yielded more well supported relationships. We present the first, well-resolved gene tree for the genus Pedioplanis and this is largely congruent with a phylogeny derived from morphology. Contrary to previous suggestions Heliobolus/Nucras are sister to Pedioplanis. The genus Pedioplanis is monophyletic, with P. burchelli/P. laticeps forming a clade that is sister to all the remaining congeners. Two distinct geographic lineages can be identified within the widespread P. namaquensis; one occurs in Namibia, while the other occurs in South Africa. The P. undata species complex is monophyletic, but one of its constituent species, P. inornata, is paraphyletic. Relationships among the subspecies of P. lineoocellata are much more complex than previously documented. An isolated population previously assigned to P. l. pulchella is paraphyletic and sister to the three named subspecies. The phylogeny identifies two biogeographical clades that probably diverged during the mid-Miocene, after the development of the Benguella Current. This probably led to habitat changes associated with climate and, in conjunction with physical barriers (Great Escarpment), contributed towards speciation within the genus Pedioplanis.