Algal symbiont shuffling in favor of more thermo-tolerant species has been shown to enhance coral resistance to heat-stress. Yet, the mechanistic underpinnings and long-term implications of these changes are poorly understood. This work studied the modifications in coral DNA methylation, an epigenetic mechanism involved in coral acclimatization, in response to symbiont manipulation and subsequent heat stress exposure. Symbiont composition was manipulated in the great star coral Montastraea cavernosa through controlled thermal bleaching and recovery, producing paired ramets of three genets dominated by either their native symbionts (genus Cladocopium) or the thermotolerant species (Durusdinium trenchi). Single-base genome-wide analyses showed significant modifications in DNA methylation concentrated in intergenic regions, introns and transposable elements. Remarkably, DNA methylation changes in response to heat stress were dependent on the dominant symbiont, with twice as many differentially methylated regions found in heat-stressed corals hosting different symbionts (Cladocopium vs. D. trenchii) compared to all other comparisons. Interestingly, while differential gene body methylation was not correlated with gene expression, an enrichment in differentially methylated regions was evident in repetitive genome regions. Overall, these results suggest that changes in algal symbionts favoring heat tolerant associations are accompanied by changes in DNA methylation in the coral host. The implications of these results for coral adaptation, along with future avenues of research based on current knowledge gaps, are discussed in the present work.