Elasmobranchs represent important components of marine ecosystems, but they can be vulnerable to overexploitation. This has driven investigations into the population genetic structure of large-bodied pelagic sharks, but relatively little is known of population structure in smaller demersal taxa, which are perhaps more representative of the biodiversity of the group. This study explores spatial population genetic structure of the small-spotted catshark (Scyliorhinus canicula), across European seas. The results show significant genetic differences among most of the Mediterranean sample collections, but no significant structure among Atlantic shelf areas. The data suggest the Mediterranean populations are likely to have persisted in a stable and structured environment during Pleistocene sea-level changes. Conversely, the Northeast Atlantic populations would have experienced major changes in habitat availability during glacial cycles, driving patterns of population reduction and expansion. The data also provide evidence of male-biased dispersal and female philopatry over large spatial scales, implying complex sex-determined differences in the behaviour of elasmobranchs. On the basis of this evidence, we suggest that patterns of connectivity are determined by trends of past habitat stability that provides opportunity for local adaptation in species exhibiting philopatric behaviour, implying that resilience of populations to fisheries and other stressors may differ across the range of species.