Coral reefs track sea level and are particularly sensitive to changes in climate. Reefs are threatened by global warming, with many experiencing increased coral bleaching. Warmer sea surface temperatures might enable reef expansion into mid latitudes. Here we report multibeam sonar and coring that reveal an extensive relict coral reef around Lord Howe Island, which is fringed by the southernmost reef in the Pacific Ocean. The relict reef, in water depths of 25–50 m, flourished in early Holocene and covered an area more than 20 times larger than the modern reef. Radiocarbon and uranium-series dating indicates that corals grew between 9000 and 7000 years ago. The reef was subsequently drowned, and backstepped to its modern limited extent. This relict reef, with localised re-establishment of corals in the past three millennia, could become a substrate for reef expansion in response to warmer temperatures, anticipated later this century and beyond, if corals are able to recolonise its surface.