Black corals are important habitat-forming species in the mesophotic and deep-sea zones of the world's oceans because of their arborescent colony structure and tendency to form animal forests. Although we have started unraveling the ecology of mesophotic black corals, the importance of the associated microbes to their health has remained unexplored. Here, we provide in-depth assessments of black coral-microbe symbioses by investigating the spatial and temporal stability of these associations, and make comparisons with a sympatric octocoral with similar colony structure. To this end, we collected samples of colonies from three mesophotic shoals situated along the Ligurian Coast of the Mediterranean Sea (Bordighera, Portofino, Savona) in the spring of 2017. At the Portofino shoal, samples of and the gorgonian were collected in November 2016 and May 2017. Bacterial communities were profiled using 16S rRNA gene amplicon sequencing. The bacterial community of was consistently dominated by . Contrastingly, the black coral microbiome was more diverse, and was primarily composed of numerous Bacteroidetes, Alpha- and Gammaproteobacterial taxa, putatively involved in all steps of the nitrogen and sulfur cycles. Compositional differences in the microbiome existed between all locations and both time points, and no phylotypes were consistently associated with . This highlights that local conditions may influence the bacterial community structure and potentially nutrient cycling within the holobiont. But it also suggests that this coral holobiont possesses a high degree of microbiome flexibility, which may be a mechanism to acclimate to environmental change.