Tropical south-western Pacific temperatures are of vital importance to the Great Barrier Reef (GBR), but the role of sea surface temperatures (SSTs) in the growth of the GBR since the Last Glacial Maximum remains largely unknown. Here we present records of Sr/Ca and delta O-18 for Last Glacial Maximum and deglacial corals that show a considerably steeper meridional SST gradient than the present day in the central GBR. We find a 1-2 degrees C larger temperature decrease between 17 degrees and 20 degrees S about 20,000 to 13,000 years ago. The result is best explained by the northward expansion of cooler subtropical waters due to a weakening of the South Pacific gyre and East Australian Current. Our findings indicate that the GBR experienced substantial meridional temperature change during the last deglaciation, and serve to explain anomalous deglacial drying of northeastern Australia. Overall, the GBR developed through significant SST change and may be more resilient than previously thought.