In the last 20 years, new species, asexual reproduction, polyploidy and hybridization have all been reported within the genus Cobitis. An understanding of the current distribution and baseline phylogeographical history of 'true' nonhybrid Cobitis species is crucial in order to unravel these discoveries. In the present work, we investigated the phylogeography of the spined loach, Cobitis taenia, using 1126 bp of the mitochondrial cytochrome b gene from 174 individuals collected at 47 sites. In total, 51 haplotypes that differed at 49 positions (4.35%) were detected. We deduce that C. taenia survived European glaciations in at least three refugees in the Ponto-Caspian area. Two of these refugees each provided a major lineage that recolonized Europe in separate directions: one westward to England and the other spreading north into Russia before moving west. A third (minor) lineage that contributed little to the recolonization of Europe was also revealed--remaining near its Black Sea refuge. However, more recent history was difficult to resolve with colonization from a more western refugium during the last glacial maximum (LGM) a distinct possibility. Nested clade analysis indicates a pattern of restricted gene flow with isolation by distance at the first two levels and overall. Unlike many other European freshwater fish species, the Danube is not part of the current distribution of C. taenia, nor was it used as either a refuge or a source of colonization of Europe. Low genetic diversity within C. taenia suggests that its colonization of Europe is relatively recent. Demographic analyses revealed a history of recent expansion and isolation by distance.