Understanding the evolution of coral heat tolerance is of prime importance for coral conservation and restoration and is an exciting challenge for evolutionary biology. In our recent genome-wide association study (GWAS) of a reef-building coral Acropora millepora we have found that the type of symbiont hosted by the coral (Cladocopium versus Durusdinium) has a larger influence on the coral’s bleaching tolerance than the coral’s genome sequence. Here, we revisit the same data with a different analytical methodology and demonstrate that the coral genome strongly influences the type of symbiont it is associated with. Based on a coral’s genome sequence, we can predict whether it will be dominated by Cladocopium or Durusdinium, with the accuracy exceeding 80%. This suggests that coral adaptation to climate change may be more strongly driven by evolution of symbionts and new coral-symbiont associations relative to the evolution of heat tolerance by the coral host.