Population structuring in species inhabiting marine environments such as the Northeast Atlantic Ocean (NEA) and Mediterranean Sea (MS) has usually been explained based on past and present physical barriers to gene flow and isolation by distance (IBD). Here, we examined the relative importance of these factors on population structuring of the common cuttlefish Sepia officinalis by using methods of phylogenetic inference and hypothesis testing coupled with coalescent and classical population genetic parameter estimation. Individuals from 10 Atlantic and 15 Mediterranean sites were sequenced for 659 bp of the mitochondrial COI gene (259 sequences). IBD seems to be the main factor driving present and past genetic structuring of Sepia populations across the NEA-MS, both at large and small geographical scales. Such an evolutionary process agrees well with some of the biological features characterizing this cuttlefish species (short migrations, nektobenthic habit, benthic eggs hatching directly to benthic juveniles). Despite the many barriers to migration/gene flow suggested in the NEA-MS region, genetic population fragmentation due to past isolation of water masses (Pleistocene; 0.56 million years ago) and/or present-day oceanographic currents was only detected between the Aegean-Ionian and western Mediterranean Seas. Restricted gene flow associated with the Almería-Oran hydrographic front was also suggested between southern and eastern Spanish populations. Distinct population boundaries could not be clearly determined, except for the Aegean-Ionian stock. Two Atlantic and five Mediterranean samples showed evidence of current decline in genetic diversity, which may indicate over-exploitation of Sepia in both marine regions.