The rockpool shrimp Palaemon elegans is an ecologically important crustacean species within the European coastline fauna. In the present study, genetic diversity and population structure and connectivity were assessed by examining 21 polymorphic microsatellite loci at 13 sampling sites located along the natural distribution range. All localities showed similar levels of genetic variability. Significant deficits of heterozygosity were recorded, most likely due to the presence of null alleles. Genetic structure analyses revealed two clearly genetically distinct groups within P. elegans but without following any geographical or oceanographic basis. Thus, our results provided nuclear evidence for the existence of a Mediterranean cryptic species within P. elegans, highlighting the need to revise its taxonomic status. Regarding P. elegans sensu stricto, population structuring was reported across the Atlantic-Mediterranean transition area, where the Almería-Orán Front restricts the gene flow between the Atlantic and the Mediterranean population. Moreover, while population connectivity was suggested between all Mediterranean localities, some substructure was found within the Atlantic group. Canary Islands exhibited a weak but significant genetic differentiation from all Atlantic mainland localities, consistent with the isolation-by-distance pattern detected throughout the Atlantic population. Overall, all these findings provided new insights into the population biology of P. elegans complex.