Allozymes and sequencing of mitochondrial cytochrome b (cyt b) and 12S genes were used to reconstruct the genetic structure and phylogenetic relationships of all Discoglossus taxa described so far (except the probably extinct D. nigriventer). This is the first time that a comprehensive study on the Discoglossus painted frogs has used nuclear and mitochondrial markers, evidencing a discordant pattern between the two datasets. Comparison of these discrepancies suggests a role of stochastic sorting of ancestral polymorphisms, possibly associated with male-biased dispersal and present or past secondary contact. The genetic relationships between taxa with intermediate levels of divergence were well defined by allozyme data, but showed short internodes and low bootstrap values for mitochondrial data, suggesting a rapid radiation of their lineages during the Messinian Lago Mare phase. The results provide information about the taxonomic status of D. galganoi and D. jeanneae, considered as subspecies, and indicate D. pictus as nonmonophyletic, confirming D. scovazzi as a distinct species.