Coral bleaching, i.e., the loss of photosynthetic algal endosymbionts, caused by ocean warming is now among the main factors driving global reef decline, making the elucidation of factors that contribute to thermotolerance important. Recent studies implicate high salinity as a contributing factor in cnidarians, potentially explaining the high thermotolerance of corals from the Arabian Seas. Here we characterized bacterial community composition under heat stress at different salinities using the coral model Aiptasia. Exposure of two Aiptasia host-algal symbiont pairings (H2-SSB01 and CC7-SSA01) to ambient (25°C) and heat stress (34°C) temperatures at low (36 PSU), intermediate (39 PSU), and high (42 PSU) salinities showed that bacterial community composition at high salinity was significantly different, concomitant with reduced bleaching susceptibility in H2-SSB01, not observed in CC7-SSA01. Elucidation of bacteria that showed increased relative abundance at high salinity, irrespective of heat stress, revealed candidate taxa that could potentially contribute to the observed increased thermotolerance. We identified 4 (H2-SSB01) and 3 (CC7-SSA01) bacterial taxa belonging to the orders Alteromonadales (1 OTU), Oligoflexales (1 OTU), Rhizobiales (2 OTUs), and Rhodobacterales (2 OTUs), suggesting that only few bacterial taxa are potential contributors to an increase in thermal tolerance at high salinities. These taxa have previously been implicated in nitrogen and DMSP cycling, processes that are considered to affect thermotolerance. Our study demonstrates microbiome restructuring in symbiotic cnidarians under heat stress at different salinities. As such, it underlines how host-associated bacterial communities adapt to prevailing environmental conditions with putative consequences for the environmental stress tolerance of the emergent metaorganism.