Coral populations in the world’s warmest reefs, the Persian/Arabian Gulf (PAG), represent an ideal model system to understand the evolutionary response of coral populations to past and present environmental change and to identify genomic loci that contribute to elevated thermal tolerance. Here, we use population genomics of the brain coral Platygyra daedalea to show that corals in the PAG represent a distinct subpopulation that was established during the Holocene marine transgression, and identify selective sweeps in their genomes associated with thermal adaptation. We demonstrate the presence of positive and disruptive selection and provide evidence for selection of differentially methylated haplotypes. While demographic analyses suggest limited potential for genetic rescue of neighboring Indian Ocean reefs, the presence of putative targets of selection in corals outside of the PAG offers hope that loci associated with thermal tolerance may be present in the standing genetic variation.