Spadefoot toads (Pelobates) and Parsley frogs (Pelodytes) are an enigmatic group of Western Palaearctic anurans. In the genus Pelobates, a fossorial lifestyle has enforced a conserved bauplan that masks their intraspecific evolutionary history. We used partial sequences of the mitochondrial 16S and 12S rRNA genes to infer a paleobiogeographic scenario of speciation events in these two anuran genera. Based on two alternative, mutually exclusive calibrations of the Iberian-African split within Pelobates (Pb. cultripes and Pb. varaldii), the disjunction of the Betic Cordillera ca. 14-16 million years ago (mya), and the end of the Messinian Salinity crisis 5.33 mya, we inferred alternative scenarios for species evolution within both genera applying regression-based dating and Bayesian molecular dating. Pelobates and Pelodytes are both monophyletic genera. Interspecific relationships among spadefoot toads are poorly resolved, and only an Iberian-African Pb. cultripes/Pb. varaldii clade consistently emerges from our analyses. An evolutionary scenario based on the Messinian divergence of African and Iberian Pelobates lineages becomes plausible in the light of geological and paleontological data. Consequently, Pelobates species are likely to have originated from the Miocene. Speciation around the Oligocene/Miocene boundary is inferred for the Iberian-Caucasian Pelodytes, and a Messinian divergence has to be invoked to explain intraspecific diversification of Iberian parsley frogs. There is indication that the different Pb. syriacus lineages may not form a monophylum.