Competition for space between corals and macroalgae represents a key threatening process for coral reefs, yet the influence of climate change on this competitive interaction is poorly understood, particularly at the poleward margins of coral distribution. Here we describe the discovery of Australia’s southernmost hermatypic corals and explore novel dynamics facilitating the presence and extent of high-latitude coral communities. Examination of 607 shallow reef sites across temperate Australia revealed hard corals to be negatively associated with increasing kelp bed cover, but positively associated with increasing sea surface temperature, herbivorous fishes, grazing sea urchins, and increasing cover of turf algae, which proliferates in the absence of kelp. However, the nature of these effects varied across different regions of temperate Australia consistent with regional variability in the presence/absence of key functional groups for temperate reefs, such as guilds of subtropical herbivorous fishes and/or prevalence of overgrazing sea urchins. For the southernmost coral communities, in eastern Bass Strait Tasmania, the dominant reef-building coral Plesiastrea versipora was negatively associated with kelp and positively associated with the southward range-extending diadematid sea urchin Centrostephanus rodgersii, which has caused extensive kelp bed overgrazing since first locally reported in 1974. Facilitation of coral establishment was strongest on overgrazed barrens where urchin density was relatively low, but sufficient to maintain the reef kelp-free, while corals were less frequent at high urchin densities and completely absent from barrens colonised by intensively grazing limpets. In contrast to tropical Australian coral reefs and other temperate regions (e.g. Western Australia), assays of herbivory confirmed sea urchin grazing, not herbivorous fishes, as chiefly responsible for kelp consumption within this high-latitude system. Size structure of P. versipora in eastern Bass Strait was dominated by small colonies (~ 20 cm2), suggesting an expanding population at the poleward edge of the species’ range. Nevertheless, colonies up to a maximum area of 500 cm2 were observed, which are likely > 40 yrs old based on growth rates established in warmer waters. This research highlights novel patterns and processes structuring the interface between subtropical and temperate reef communities under climate change and specifically highlights the role of herbivores in releasing corals from competition with kelp under warming ocean regimes.