The common octopus, Octopus vulgaris Cuvier 1797, is a largely exploited cephalopod species in the Mediterranean Sea and the Atlantic Ocean, as well as along the coasts of Africa, Brazil and Japan, where its taxonomic identity is still debated. The assessment of its genetic structure is a pressing need to correctly manage the resource and to avoid overfishing and collapsing of local stocks. Here we analysed genetic variation and population structure of O. vulgaris using thirteen microsatellite loci in seven sampling localities from the Mediterranean Sea and one from the Atlantic Ocean. We also used a DNA barcoding approach by COI gene fragment to understand the phylogenetic relationships among the specimens here investigated and the ones whose sequences are available in literature. Our results reveal high levels of allelic richness and moderate heterozygosity in all samples investigated, and a pronounced differentiation of the Atlantic and Sicilian specimens. This latter aspect seems to support the isolation of the biota within the Strait of Messina. A certain degree of differentiation was detected among the other geographic samples within the Mediterranean Sea, which is more compatible with an island model than isolation by distance. The occurrence of null alleles affected more genetic diversity indices than population structure estimations. This study provides new insights about the genetic diversity and structure of O. vulgaris in the area of interest, which can be used as guidelines for a fisheries management perspective.