The formation of continental Europe in the Neogene was due to the regression of the Tethys Ocean and of the Paratethys Sea. The dynamic geology of the area and repetitious transitions between marine and freshwater conditions presented opportunities for the colonization of newly emerging hydrological networks and diversification of aquatic biota. Implementing mitochondrial and nuclear markers in conjunction with a large-scale sampling strategy, we investigated the impact of this spatiotemporal framework on the evolutionary history of a freshwater crustacean morphospecies. The Gammarus balcanicus species complex is widely distributed in the area previously occupied by the Paratethys Sea. Our results revealed its high diversification and polyphyly in relation to a number of other morphospecies. The distribution of the studied amphipod is generally characterized by very high local endemism and divergence. The Bayesian time-calibrated reconstruction of phylogeny and geographical distribution of ancestral nodes indicates that this species complex started to diversify in the Early Miocene in the central Balkans, partially in the shallow epicontinental sea. It is possible that there were several episodes of inland water colonization by local brackish water lineages. Subsequent diversification within clades and spread to new areas could have been induced by Alpine orogeny in the Miocene/Pliocene and, finally, by Pleistocene glaciations. The present distribution of clades, in many cases, still reflects Miocene palaeogeography of the area. Our results point out that investigations of the historical aspect of cryptic diversity in other taxa may help in a general understanding of the origins of freshwater invertebrate fauna of Europe.