Palearctic water frogs (genus Pelophylax) are an outstanding model in ecology and evolution, being widespread, speciose, either threatened or threatening to other species through biological invasions, and capable of siring hybrid offspring that escape the rules of sexual reproduction. Despite half a century of genetic research and hundreds of publications, the diversity, systematics and biogeography of Pelophylax still remain highly confusing, in no small part due to a lack of correspondence between studies. To provide a comprehensive overview, we gathered >13,000 sequences of barcoding genes from >1700 native and introduced localities and built multigene mitochondrial (~17 kb) and nuclear (~10 kb) phylogenies. We mapped all currently recognized taxa and their phylogeographic lineages (>40) to get a grasp on taxonomic issues, cyto-nuclear discordances, the genetic makeup of hybridogenetic hybrids, and the origins of introduced populations. Competing hypotheses for the molecular calibration were evaluated through plausibility tests, implementing a new approach relying on predictions from the anuran speciation continuum. Based on our timetree, we propose a new biogeographic paradigm for the Palearctic since the Paleogene, notably by attributing a prominent role to the dynamics of the Paratethys, a vast paleo-sea that extended over most of Europe. Furthermore, our results show that distinct marsh frog lineages from Eastern Europe, the Balkans, the Near East, and Central Asia (P. ridibundus ssp.) are naturally capable of inducing hybridogenesis with pool frogs (P. lessonae). We identified 14 alien lineages (mostly of P. ridibundus) over ~20 areas of invasions, especially in Western Europe, with genetic signatures disproportionally pointing to the Balkans and Anatolia as the regions of origins, in line with exporting records of the frog leg industry and the stocks of pet sellers. Pelophylax thus emerges as one of the most invasive amphibians worldwide, and deserves much higher conservation concern than currently given by the authorities fighting biological invasions.