Sea surface temperature (SST) across much of the tropics has increased by 0.4 degrees to 1 degrees C since the mid-1970s. A parallel increase in the frequency and extent of coral bleaching and mortality has fueled concern that climate change poses a major threat to the survival of coral reef ecosystems worldwide. Here we show that steadily rising SSTs, not ocean acidification, are already driving dramatic changes in the growth of an important reef-building coral in the central Red Sea. Three-dimensional computed tomography analyses of the massive coral Diploastrea heliopora reveal that skeletal growth of apparently healthy colonies has declined by 30% since 1998. The same corals responded to a short-lived warm event in 1941/1942, but recovered within 3 years as the ocean cooled. Combining our data with climate model simulations by the Intergovernmental Panel on Climate Change, we predict that should the current warming trend continue, this coral could cease growing altogether by 2070.