Gorgonians are key habitat-forming species of Mediterranean benthic communities, but their populations have suffered from mass mortality events linked to high summer seawater temperatures and microbial disease. However, our knowledge on the diversity, dynamics and function of gorgonian-associated microbial communities is limited. Here, we analysed the spatial variability of the microbiomes of five sympatric gorgonian species (Eunicella singularis, Eunicella cavolini, Eunicella verrucosa, Leptogorgia sarmentosa and Paramuricea clavata), collected from the Mediterranean Sea over a scale of ∼1100 km, using next-generation amplicon sequencing of the 16S rRNA gene. The microbiomes of all gorgonian species were generally dominated by members of the genus Endozoicomonas, which were at very low abundance in the surrounding seawater. Although the composition of the core microbiome (operational taxonomic units consistently present in a species) was found to be unique for each host species, significant overlap was observed. These spatially consistent associations between gorgonians and their core bacteria suggest intricate symbiotic relationships and regulation of the microbiome composition by the host. At the same time, local variations in microbiome composition were observed. Functional predictive profiling indicated that these differences could be attributed to seawater pollution. Taken together, our data indicate that gorgonian-associated microbiomes are composed of spatially conserved bacteria (core microbiome members) and locally variant members, and that local pollution may influence these local associations, potentially impacting gorgonian health.