Chemical analysis of deepwater octocorals collected at 1000 m depth off southern Australia indicates long-term cooling, beginning in the mid-18th century. This cooling appears to reflect shoaling of isotherms along the continental shelf, that can be related statistically, observationally and by modeling to increasing coastal sea-surface temperatures, that in turn reflect a poleward extension of the SW Pacific boundary current (the East Australian Current). The oceanographic changes implied by the coral record suggest climate change in temperate Australia starting about the time of European settlement. Correlations between temperate Australian and Antarctic indices suggest these long-term changes might also be relevant to Antarctic climate.