Despite increases in the frequency and intensity of disturbances on coral reefs over the past few decades, the response of subtropical coral assemblages to climate change is poorly understood. To address this knowledge gap on Australian reefs and provide a baseline for future comparisons, we quantified spatial (10-100's of kilometres) and temporal (decadal) patterns of benthic assemblages across a latitudinal gradient along the east Australian coastline (23.5° S to 31.5° S). Benthic community composition was quantified at six locations from the southern Great Barrier Reef, Queensland (Heron Reef, 23.5° S, 152° E) to northern New South Wales (31° S, 153.1° E) and at Lord Howe Island (31.5° S, 159.1° E). Our results indicate significant latitudinal differences in benthic assemblages, while community composition at some sites was more similar to those hundreds of kilometres away than to that of neighbouring reefs. A general trend was observed with decreasing cover of Acroporidae with increasing latitude, corresponding with an increasing cover of Pocilloporidae and Dendrophylliidae. Heron Reef comprised a high proportion of Acropora corals (43% total coral cover) and coralline algae (44%). In contrast, high-latitude reefs were dominated by mixed coral assemblages (0-52%) and high macroalgal cover (16-27%). Decadal comparisons of high-latitude reefs showed regional stability of benthic assemblages (9 out of 11 assemblages remained stable at > 75% similarity), during a period of warming oceans (0.15-0.24°C per decade). Such temporal stability suggests that eastern Australian subtropical communities may be more resistant than tropical reef communities that have experienced assembly shifts caused by perturbations associated with recent global climate change. Despite the clear differences in the structure of coral assemblages evident in our spatial surveys, we suggest that the temporal stability of high-latitude reefs may provide a limited refuge for tropical coral populations in an increasingly uncertain future.