Mutualistic organisms can be particularly susceptible to climate change stress, as their survivorship is often limited by the most vulnerable partner. However, symbiotic plasticity can also help organisms in changing environments by expanding their realized niche space. Coral–algal (Symbiodinium spp.) symbiosis exemplifies this dichotomy: the partnership is highly susceptible to ‘bleaching’ (stress-induced symbiosis breakdown), but stress-tolerant symbionts can also sometimes mitigate bleaching. Here, we investigate the role of diverse and mutable symbiotic partnerships in increasing corals' ability to thrive in high temperature conditions. We conducted repeat bleaching and recovery experiments on the coral Montastraea cavernosa, and used quantitative PCR and chlorophyll fluorometry to assess the structure and function of Symbiodinium communities within coral hosts. During an initial heat exposure (32 °C for 10 days), corals hosting only stress-sensitive symbionts (Symbiodinium C3) bleached, but recovered (at either 24 °C or 29 °C) with predominantly (>90%) stress-tolerant symbionts (Symbiodinium D1a), which were not detected before bleaching (either due to absence or extreme low abundance). When a second heat stress (also 32 °C for 10 days) was applied 3 months later, corals that previously bleached and were now dominated by D1a Symbiodinium experienced less photodamage and symbiont loss compared to control corals that had not been previously bleached, and were therefore still dominated by Symbiodinium C3. Additional corals that were initially bleached without heat by a herbicide (DCMU, at 24 °C) also recovered predominantly with D1a symbionts, and similarly lost fewer symbionts during subsequent thermal stress. Increased thermotolerance was also not observed in C3-dominated corals that were acclimated for 3 months to warmer temperatures (29 °C) before heat stress. These findings indicate that increased thermotolerance post-bleaching resulted from symbiont community composition changes, not prior heat exposure. Moreover, initially undetectable D1a symbionts became dominant only after bleaching, and were critical to corals' resilience after stress and resistance to future stress.