The red gorgonian Paramuricea clavata plays a central role in coralligenous ecosystems of the Mediterranean Sea, being relatively abundant in shallow habitats (5–35 m depth). Recently, deeper populations have been discovered at the heads of submarine canyons in the northwestern Mediterranean Sea, between 50 and 70 m deep. Colonies from some of these deeper populations were exceptionally large ([1 m high), contrasting with the general prevalence of smaller size classes in shallower populations. Importantly, the high pressure of trawling activities on the nearby continental shelf could threaten these populations of large and old colonies. Although the genetic diversity and structure of populations in shallow habitats is relatively well known, very little is known about deeper populations. We aimed to assess the genetic structure, connectivity and potential demographic decline of six deep populations of P. clavata located at the heads of La Fonera, Blanes and Arenys de Mar submarine canyons, as well as potential gene flow between those and the two nearest shallow populations. A total of 188 individuals were genotyped using nine microsatellite loci. Results showed strong genetic differentiation among populations in different submarine canyons, among populations within one of the canyons and between shallow and deep populations. Gene flow among populations was very limited, estimates of effective population size in some populations were small, and evidence of recent population reductions (bottlenecks) was detected in several populations. The large genetic differentiation in populations of P. clavata among canyons is related to limited effective dispersal.