The genetic structure of European mudminnow populations throughout the species range was examined using mitochondrial DNA and seven microsatellite loci. Ten mitochondrial haplotypes were detected, suggesting three phylogeographic lineages, which likely diverged during the Early and Middle Pleistocene. These three lineages geographically correspond to three regions: the Danube drainage including the Drava system and Dniester Delta, the Sava system and the Tisza system. High genetic diversity observed using mtDNA was confirmed with microsatellite data, suggesting the existence of 14 populations in the studied area. The isolation-with-migration model showed that migration rates between populations were generally low and were highest between the Drava and its tributary Mura. According to the inferred relative population splitting times, Umbra krameri likely spread from the eastern part of the species range to the west, which also showed the highest genetic diversity and largest population size. As reported by the time-calibrated phylogeny, separation of the European and American Umbra occurred roughly at the end of Late Cretaceous and in the first half of the Paleogene (60.57 Ma with 95% highest probability density of 39.57–81.75). Taking these results into account, appropriate guidelines are proposed to conserve European mudminnow populations.