The current lack of understanding of the genetic basis underlying environmental stress tolerance in reef-building corals impairs the development of new management approaches to confronting the global demise of coral reefs. On the Great Barrier Reef (GBR), an approximately 51% decline in coral cover occurred over the period 1985-2012. We conducted a gene-by-environment association analysis across 12 latitude on the GBR, as well as both in situ and laboratory genotype-by-phenotype association analyses. These analyses allowed us to identify alleles at two genetic loci that account for differences in environmental stress tolerance and antioxidant capacity in the common coral Acropora millepora. The effect size for antioxidant capacity was considerable and biologically relevant (32.5 and 14.6% for the two loci). Antioxidant capacity is a critical component of stress tolerance because a multitude of environmental stressors cause increased cellular levels of reactive oxygen species. Our findings provide the first step toward the development of novel coral reef management approaches, such as spatial mapping of stress tolerance for use in marine protected area design, identification of stress-tolerant colonies for assisted migration, and marker-assisted selective breeding to create more tolerant genotypes for restoration of denuded reefs.