Aim We explore the genetic structure of the widespread starfish, Marthasterias spp., in order to: (1) identify historical causes of genetic divergence, (2) test the effect of past climatic events on populations’ demography and (3) explore main barriers to gene flow. Location North- and south-east Atlantic Ocean and Mediterranean Sea. Methods We amplified and sequenced three mitochondrial genes and one nuclear intron, and genotyped five nuclear microsatellite loci from 337 specimens. We reconstructed the phylogeny and phylogeography of Marthasterias spp. using the obtained DNA sequences, and used the microsatellite loci to explore major genetic discontinuities along the European coast. Results Our results suggested the existence of two allopatric species, one in the Northern Hemisphere (M. glacialis) and another in the Southern Hemisphere (Marthasterias sp.). This allopatric split could be attributed to recent changes in oceanographic circulation of the eastern Atlantic Ocean that may have acted as barrier to gene flow. Mitochondrial divergence between European lineages could be attributed to potential vicariance during Pleistocene glacial periods, but was not supported by nuclear markers, which may be indicative of recent genetic admixture. Secondary contact after glacial periods and gene flow across the Gibraltar Strait may explain this pattern. Genetic structure of M. glacialis based on nuclear markers did not show much divergence among geographical areas although most populations were significantly differentiated. Main conclusions The phylogeography of the widely distributed genus Marthasterias has most likely been shaped by recent changes in climate and oceanographic patterns. Major changes of ocean current patterns initially resulted in splitting between Northern and Southern Hemisphere lineages. Subsequently, glacial periods most likely enhanced vicariance of European lineages, followed by a post-glacial expansion facilitating secondary contacts and genetic admixture.