The lacertid genus Pedioplanis is a moderately speciose group of small-bodied, cryptically-colored lizards found in arid habitats throughout southern Africa. Previous phylogenetic work on Pedioplanis has determined its placement within the broader context of the Lacertidae, but interspecific relations within the genus remain unsettled, particularly within the P. undata species complex, a group largely endemic to Namibia. We greatly expanded taxon sampling for members of the P. undata complex and other Pedioplanis, and generated molecular sequence data from 1,937 bp of mtDNA (ND2 and cyt b) and 2,015 bp of nDNA (KIF24, PRLR, RAG-1) which were combined with sequences from GenBank resulting in a final dataset of 455 individuals. Both maximum likelihood and Bayesian analyses recover similar phylogenetic results and reveal the polyphyly of P. undata and P. inornata as presently construed. We confirm that P. husabensis is sister to the group comprising the P. undata complex plus the Angolan sister species P. huntleyi + P. haackei and demonstrate that P. benguelensis lies outside of this clade in its entirety. The complex itself comprises six species including P. undata, P. inornata, P. rubens, P. gaerdesi and two previously undescribed entities. Based on divergence date estimates, the P. undata species complex began diversifying in the late Miocene (5.3 ± 1.6 MYA) with the most recent cladogenetic events dating to the Pliocene (2.6 ± 1.0 MYA), making this assemblage relatively young compared to the genus Pedioplanis as a whole, the origin of which dates back to the mid-Miocene (13.5 ± 1.8 MYA). Using an integrative approach, we here describe Pedioplanis branchi sp. nov. and Pedioplanis mayeri sp. nov. representing northern populations previously assigned to P. inornata and P. undata, respectively. These entities were first flagged as possible new species by Berger-Dell’mour and Mayer over thirty years ago but were never formally described. The new species are supported chiefly by differences in coloration and by unique amino acid substitutions. We provide comprehensive maps depicting historical records based on museum specimens plus new records from this study for all members of the P. undata complex and P. husabensis. We suggest that climatic oscillations of the Upper Miocene and Pliocene-Pleistocene era in concert with the formation of biogeographic barriers have led to population isolation, gene flow restrictions and ultimately cladogenesis in the P. undata complex.