Mass mortality events in populations of the iconic red coral Corallium rubrum have been related to seawater temperature anomalies that may have triggered microbial disease development. However, very little is known about the bacterial community associated with the red coral. We therefore aimed to provide insight into this species’ bacterial assemblages using Illumina MiSeq sequencing of 16S rRNA gene amplicons generated from samples collected at five locations distributed across the western Mediterranean Sea. Twelve bacterial species were found to be consistently associated with the red coral, forming a core microbiome that accounted for 94.6% of the overall bacterial community. This core microbiome was particularly dominated by bacteria of the orders Spirochaetales and Oceanospirillales, in particular the ME2 family. Bacteria belonging to these orders have been implicated in nutrient cycling, including nitrogen, carbon and sulfur. While Oceanospirillales are common symbionts of marine invertebrates, our results identify members of the Spirochaetales as other important dominant symbiotic bacterial associates within Anthozoans.