The Black and Caspian Seas have experienced alternating periods of isolation and interconnection over many Milankovitch climate oscillations and most recently became separated when the meltwater overflow from the Caspian Sea ceased at the end of the last glaciation. Climate-induced habitat changes have indisputably had profound impacts on distribution and demography of aquatic species, yet uncertainties remain about the relative roles of isolation and dispersal in the response of species shared between the Black and Caspian Sea basins. We examined these issues using phylogeographical analysis of an anadromous cyprinid fish Rutilus frisii. Bayesian coalescence analyses of sequence variation at two nuclear and one mitochondrial genes suggest that the Black and Caspian Seas supported separate populations of R. frisii during the last glaciation. Parameter estimates from the fitted isolation-with-migration model showed that their separation was not complete, however, and that the two populations continued to exchange genes in both directions. These analyses also suggested that majority of migrations occurred during the Pleistocene, showing that the variation shared between the Black and Caspian Seas is the result of ancient dispersal along the temporary natural connections between the basins, rather than of incomplete lineage sorting or recent human-mediated dispersal. Gene flow between the refugial populations was therefore an important source of genetic variation, and we suggest that it facilitated the evolutionary response of the populations to changing climate.