Understanding the factors explaining the observed patterns of genetic diversity is an important question in evolutionary biology. We provide the first data on the genetic structure of a Mediterranean octocoral, the yellow gorgonian Eunicella cavolini, along with insights into the demographic history of this species. We sampled populations in four areas of the Mediterranean Sea: continental France, Algeria, Turkey, and the Balearic and Corsica islands. Along French coasts, three sites were sampled at two depths (20 and 40 m). We demonstrated a high genetic structure in this species (overall F-ST = 0.13), and most pairwise differentiation tests were significant. We did not detect any difference between depths at the same site. Clustering analyses revealed four differentiated groups corresponding to the main geographical areas. The levels of allelic richness and heterozygosity were significantly different between regions, with highest diversity in Algeria and lowest levels in Turkey. The highest levels of private allelic richness were observed in Algeria followed by Turkey. Such contrasted patterns of genetic diversity were not observed in other Mediterranean octocorals and could be the result of different evolutionary histories. We also provide new empirical evidence of contrasting results between tests and model-based studies of demographic history. Our results have important consequences for the management of this species.