Based on rangewide sampling and three mitochondrial and two nuclear markers (together up to 1,850 bp and 1,840 bp, respectively), we examine the phylogeography of two helmeted terrapin species (Pelomedusa galeata and P. subrufa sensu stricto) and infer shifts of climatically suitable spaces since the Last Glacial Maximum using a modeling approach. Whilst P. galeata displays significant phylogeographic structuring across its range and consists of two deeply divergent lineages that could represent distinct species, P. subrufa shows no obvious phylogeographic differentiation. This seems to be related to historically stable or fluctuating ranges. One of the lineages within P. galeata appears to be confined to the westernmost, winter-rainfall region of South Africa and deserves special conservational attention due to the scarcity of surface water. The other lineage is distributed further east and is differentiated in three weakly supported subclades with parapatric distribution; one occurring inland, and two along the south and east coasts, respectively. As far as is known, P. subrufa occurs in South Africa only in the northeast of the country (Limpopo, Mpumalanga) and we report the species for the first time from the Lapalala Wilderness Area in the Waterberg region (Limpopo), approximately 350 km further west than previously recorded. We confirmed the occurrence of P. galeata only 80 km south of Lapalala. Thus, a sympatric occurrence of P. galeata and P. subrufa is possible. Another putative contact zone, for the two lineages within P. galeata, must be located in the Western Cape region, and further contact zones are likely for the eastern subclades within P. galeata. The nuclear loci provided no evidence for gene flow across taxa or genetic clusters within taxa. Future investigations should use denser sampling from putative contact zones and more nuclear markers to re-examine this situation. Despite few phylogeographic studies published for southern African biota, it seems likely that differentiation follows general rules, and that climate and physiographic barriers (e.g., the Great Escarpment) have shaped phylogeographic patterns.