The coral-algal symbiosis is maintained by a constant and limited nitrogen availability in the holobiont. Denitrifiers, i.e., prokaryotes reducing nitrate/nitrite to dinitrogen, could contribute to maintaining the nitrogen limitation in the coral holobiont, however the effect of host and algal identity on their community is still unknown. Using the coral model Aiptasia, we quantified and characterized the denitrifier community in a full-factorial design combining two hosts (CC7 and H2) and two strains of algal symbionts of the family Symbiodiniaceae (SSA01 and SSB01). Strikingly, relative abundance of denitrifiers increased by up to 22-fold in photosymbiotic Aiptasia compared to their aposymbiotic (i.e., algal-depleted) counterparts. In line with this, while the denitrifier community in aposymbiotic Aiptasia was largely dominated by diet-associated Halomonas, we observed an increasing relative abundance of an unclassified bacterium in photosymbiotic CC7, and Ketobacter in photosymbiotic H2, respectively. Pronounced changes in denitrifier communities of Aiptasia with Symbiodinium linucheae strain SSA01 aligned with the higher photosynthetic carbon availability of these holobionts compared to Aiptasia with Breviolum minutum strain SSB01. Our results reveal that the presence of algal symbionts increases abundance and alters community structure of denitrifiers in Aiptasia. Thereby, patterns in denitrifier community likely reflect the nutritional status of aposymbiotic vs. symbiotic holobionts. Such a passive regulation of denitrifiers may contribute to maintaining the nitrogen limitation required for the functioning of the cnidarian-algal symbiosis.