Ocean warming threatens corals and the coral reef ecosystem. Nevertheless, corals can be adapted to their thermal environment and inherit heat tolerance across generations. In addition, the diverse microbes that associate with corals have the capacity for more rapid change, potentially aiding the adaptation of long-lived corals. Here, we show that the microbiome of reef corals is different across thermally variable habitats and changes over time when corals are reciprocally transplanted. Exposing these corals to thermal bleaching conditions changes the microbiome for heat-sensitive corals, but not for heat-tolerant corals growing in habitats with natural high heat extremes. Importantly, particular bacterial taxa predict the coral host response in a short-term heat stress experiment. Such associations could result from parallel responses of the coral and the microbial community to living at high natural temperatures. A competing hypothesis is that the microbial community and coral heat tolerance are causally linked.