Despite the importance of gelatinous zooplankton as components of marine ecosystems, both ecologically and socio-economically, relatively little information is known about population persistence or connectivity in jellyfish. In the present study, we employed a combination of nuclear microsatellite markers and sequence data from the mitochondrial cytochrome oxidase I (COI) gene to determine levels and patterns of population genetic structuring in the holoplanktonic jellyfish Pelagia noctiluca across the northeast Atlantic Ocean and Mediterranean Sea. Our results indicate a high degree of connectivity in P. noctiluca, with little evidence of geographical structuring of genetic variation. A small but significant differentiation of Atlantic Ocean and Mediterranean stocks was detected based on the microsatellite data, but no evidence of differentiation was observed with the mtDNA, probably due to the higher power of the microsatellites to detect low levels of genetic structuring. Two clearly distinct groups of genotypes were observed within the mtDNA COI, which probably diverged in the early Pleistocene, but with no evidence of geographical structuring. Palaeodistribution modelling of P. noctiluca at the Last Glacial Maximum (LGM; c. 21 Kya) indicated large areas of suitable habitat south of the species’ current-day distribution, with little reduction in area. The congruent evidence for minimal genetic differentiation from the nuclear microsatellites and the mtDNA, coupled with the results of the palaeodistribution modelling, supports the idea of long-term population stability and connectivity, thus providing key insights into the population dynamics and demography of this important species.