We report the discovery of three submerged, living patch coral reefs covering 80 km2 in the southern Gulf of Carpentaria, Australia, an area previously thought not to contain coral bioherms. The patch reefs have their upper surfaces at a mean water depth of 28.6±0.5 m, and were consequently not detected by satellites or aerial photographs. The reefs were only recognised in our survey using multibeam swath sonar supplemented with seabed sampling and under water video. Their existence points to an earlier, late Quaternary phase of framework reef growth, probably under cooler climate and lower sea level conditions than today. Submerged reefs with surfaces between 20 and 30 m water depth occur in other regions of the Earth and existing bathymetry indicates they could be widespread in the Gulf. Many tropical regions that today do not support patch or barrier reefs for reasons similar to the modern Gulf, may have done so in the past, when environmental conditions were more suitable. Submerged reefs may provide an important refuge for corals during the next few decades when near-surface reefs are threatened by widespread coral bleaching due to warmer global sea surface temperatures.