Dynamic symbioses may critically mediate impacts of climate change on diverse organisms, with repercussions for ecosystem persistence in some cases. On coral reefs, increases in heat-tolerant symbionts after thermal bleaching can reduce coral susceptibility to future stress. However, the relevance of this adaptive response is equivocal owing to conflicting reports of symbiont stability and change. We help reconcile this conflict by showing that change in symbiont community composition (symbiont shuffling) in Orbicella faveolata depends on the disturbance severity and recovery environment. The proportion of heat-tolerant symbionts dramatically increased following severe experimental bleaching, especially in a warmer recovery environment, but tended to decrease if bleaching was less severe. These patterns can be explained by variation in symbiont performance in the changing microenvironments created by differentially bleached host tissues. Furthermore, higher proportions of heat-tolerant symbionts linearly increased bleaching resistance but reduced photochemical efficiency, suggesting that any change in community structure oppositely impacts performance and stress tolerance. Therefore, even minor symbiont shuffling can adaptively benefit corals, although fitness effects of resulting trade-offs are difficult to predict. This work helps elucidate causes and consequences of dynamism in symbiosis, which is critical to predicting responses of multi-partner symbioses such as O. faveolata to environmental change.