The Atlantic-Mediterranean transition zone between the Alboran Sea and the Gulf of Cadiz constitutes the most prominent marine geographic barrier in European waters and includes known phylogeographic breaks such as the Strait of Gibraltar and the Almeria-Oran Front. A genetic shift in this area has been previously documented for the European littoral shrimp Palaemon elegans. Here we carried out a phylogeographic analysis with the congeneric and sympatric species Palaemon serratus to test for similar intraspecific genetic differentiation and geographic structure. This littoral prawn is distributed in the Northeastern Atlantic Ocean, the Mediterranean Sea and the Black Sea. We compared DNA sequences from the mitochondrial genes Cox1 and to a lesser extent from 16S rRNA of several Atlantic and Mediterranean populations. Furthermore, sequences from the nuclear gene Enolase were included for corroborating differences between Mediterranean and Atlantic individuals. A pronounced genetic differentiation was detected between the Mediterranean and Atlantic populations, amounting to 10.14% in Cox1 and 2.0% in 16S, indicating the occurrence of two independent evolutionary lineages. Interestingly, specimens from the Atlantic Gulf of Cadiz cluster together with the Mediterranean individuals, indicating that a biogeographic barrier appears to be located west of the Strait of Gibraltar.