Mutualistic nutrient cycling in the coral-algae symbiosis depends on limited nitrogen (N) availability for algal symbionts. Denitrifying prokaryotes capable of reducing nitrate or nitrite to dinitrogen could thus support coral holobiont functioning by limiting N availability. Octocorals show some of the highest denitrification rates among reef organisms; however, little is known about the community structures of associated denitrifiers and their response to environmental fluctuations. Combining 16S rRNA gene amplicon sequencing with nirS in-silico PCR and quantitative PCR, we found differences in bacterial community dynamics between two octocorals exposed to excess dissolved organic carbon (DOC) and concomitant warming. Although bacterial communities of the gorgonian Pinnigorgia flava remained largely unaffected by DOC and warming, the soft coral Xenia umbellata exhibited a pronounced shift toward Alphaproteobacteria dominance under excess DOC. Likewise, the relative abundance of denitrifiers was not altered in P. flava but decreased by 1 order of magnitude in X. umbellata under excess DOC, likely due to decreased proportions of Ruegeria spp. Given that holobiont C:N ratios remained stable in P. flava but showed a pronounced increase with excess DOC in X. umbellata, our results suggest that microbial community dynamics may reflect the nutritional status of the holobiont. Hence, denitrifier abundance may be directly linked to N availability. This suggests a passive regulation of N cycling microbes based on N availability, which could help stabilize nutrient limitation in the coral-algal symbiosis and thereby support holobiont functioning in a changing environment.