Occasional XY recombination is a proposed explanation for the sex-chromosome homomorphy in European tree frogs. Numerous laboratory crosses, however, failed to detect any event of male recombination, and a detailed survey of NW-European Hyla arborea populations identified male-specific alleles at sex-linked loci, pointing to the absence of XY recombination in their recent history. Here, we address this paradox in a phylogeographic framework by genotyping sex-linked microsatellite markers in populations and sibships from the entire species range. Contrasting with postglacial populations of NW Europe, which display complete absence of XY recombination and strong sex-chromosome differentiation, refugial populations of the southern Balkans and Adriatic coast show limited XY recombination and large overlaps in allele frequencies. Geographically and historically intermediate populations of the Pannonian Basin show intermediate patterns of XY differentiation. Even in populations where X and Y occasionally recombine, the genetic diversity of Y haplotypes is reduced below the levels expected from the fourfold drop in copy numbers. This study is the first in which X and Y haplotypes could be phased over the distribution range in a species with homomorphic sex chromosomes; it shows that XY-recombination patterns may differ strikingly between conspecific populations, and that recombination arrest may evolve rapidly (<5000 generations).