Madagascar is a biodiversity hotspot with a unique fauna and flora largely endemic at the species level and highly threatened by habitat destruction. The processes underlying population-level differentiation in Madagascar's biota are poorly understood and have been proposed to be related to Pleistocene climatic cycles, yet the levels of genetic divergence observed are often suggestive of ancient events. We combined molecular markers of different variability to assess the phylogeography of Madagascar's emblematic tomato frogs (Dyscophus guineti and D. antongilii) and interpret the observed pattern as resulting from ancient and recent processes. Our results suggest that the initial divergence between these taxa is probably old as reflected by protein-coding nuclear genes and by a strong mitochondrial differentiation of the southernmost population. Dramatic changes in their demography appear to have been triggered by the end of the last glacial period and possibly by the short return of glacial conditions known as the 8K event. This dramatic change resulted in an approximately 50-fold reduction of the effective population size in various populations of both species. We hypothesize these species' current mitochondrial DNA diversity distribution reflects a swamping of the mitochondrial genetic diversity of D. guineti by that of D. antongilii previous to the populations' bottlenecks during the Holocene, and probably as a consequence of D. antongilii demographic expansion approximately 1 million years ago. Our data support the continued recognition of D. antongilii and D. guineti as separate species and flag D. guineti as the more vulnerable species to past and probably also future environmental changes.