Intraspecific genetic diversity and divergence have a large influence on the adaption and evolutionary potential of species. The widely distributed starfish, Coscinasterias tenuispina, combines sexual reproduction with asexual reproduction via fission. Here we analyse the phylogeography of this starfish to reveal historical and contemporary processes driving its intraspecific genetic divergence. We further consider whether asexual reproduction is the most important method of propagation throughout the distribution range of this species. Our study included 326 individuals from 16 populations, covering most of the species’ distribution range. A total of 12 nuclear microsatellite loci and sequences of the mitochondrial cytochrome c oxidase subunit I (COI) gene were analysed. COI and microsatellites were clustered in two isolated lineages: one found along the south-western Atlantic and the other along the north-eastern Atlantic and Mediterranean Sea. This suggests the existence of two different evolutionary units. Marine barriers along the European coast would be responsible for population clustering: the Almeria-Oran Front that limits the entrance of migrants from the Atlantic to the Mediterranean, and the Siculo Tunisian strait that divides the two Mediterranean basins. The presence of identical genotypes was detected in all populations, although two monoclonal populations where found in two sites where annual mean temperatures and minimum values were the lowest. Our results based on microsatellite loci showed that intra-population genetic diversity was significantly affected by clonality whereas it had lower effect for the global phylogeography of the species, although still some impact on populations’ genetic divergence could be observed between some populations.