The remarkably discontinuous distribution of the cave shrimp genus Troglocaris in South France, West Balkans, and West Caucasus has long been considered a biogeographic enigma. To solve it, its phylogeny was reconstructed by analyzing sequences from two mitochondrial (cytochrome oxidase I and 16S rRNA) and one nuclear gene (28S rRNA) using maximum likelihood, parsimony and Bayesian inference. The genus was found to be polyphyletic because the French taxon T. inermis had no direct common ancestry with other Troglocaris taxa but was sister to the epigean freshwater atyid Dugastella valentina. All other Troglocaris species constituted a well-supported monophylum, the second cave shrimp genus Spelaeocaris nested within. The monophylum had a well-defined structure: (1) a clade restricted to the Dinaric area of the Western Balkans containing the type species T. anophthalmus along with some unnamed species, and (2) a geographically mixed clade split between the Caucasian T. kutaissiana species complex on one, and T. hercegovinensis, S. pretneri, plus an unnamed taxon on the other side. It was surprising to find the dichotomy between the Caucasian and one of the West-Balkan lineages so low in the phylogenetic hierarchy of the genus. Taking into account molecular rates of other decapods, we tentatively dated this split at 6-11 Myr. This time is in agreement with the brackish and freshwater phase of the Paratethys thus allowing for a freshwater common ancestor of Caucasian and Dinaric cave shrimps. This would weaken the marine relicts hypothesis that has often been invoked to explain the distribution of freshwater cave species with close marine relatives.