The marine cave-dwelling mysid Hemimysis margalefi is distributed over the whole Mediterranean Sea which contrasts with the poor dispersal capabilities of this brooding species. In addition, underwater marine caves are a highly fragmented habitat which further promotes strong genetic structuring, therefore providing highly informative data on the levels of marine population connectivity across biogeographic regions. This study investigates how habitat and geography have shaped the connectivity network of this poor disperser over the entire Mediterranean Sea through the use of several mitochondrial and nuclear markers. Five deeply divergent lineages were observed among H. margalefi populations resulting from deep phylogeographic breaks, some dating back to the Oligo-Miocene. Whether looking at the intra-lineage or inter-lineage levels, H. margalefi populations present a high genetic diversity and population structuring. This study suggests that the five distinct lineages observed in H. margalefi actually correspond to as many separate cryptic taxa. The nominal species, H. margalefi sensu stricto, corresponds to the westernmost lineage here surveyed from the Alboran Sea to south-eastern Italy. Typical genetic breaks such as the Almeria-Oran Front or the Sicilo-Tunisian Strait do not appear to be influential on the studied loci in H. margalefi sensu stricto. Instead, population structuring appears more complex and subtle than usually found for model species with a pelagic dispersal phase. The remaining four cryptic taxa are all found in the eastern basin, but incomplete lineage sorting is suspected and speciation might still be in process. Present day population structure of the different H. margalefi cryptic species appears to result from past vicariance events started in the Oligo-Miocene and maintained by present day coastal topography, water circulation and habitat fragmentation.