Occupying 14% of the world’s surface, the Southern Ocean plays a fundamental role in global climate, ocean circulation, carbon cycling and Antarctic ice-sheet stability. Unfortunately, high interannual variability and a dearth of instrumental observations before the 1950s limits our understanding of how marine-atmosphere-ice domains interact on multi-decadal timescales and the impact of anthropogenic forcing. Here we integrate climate-sensitive tree growth with ocean and atmospheric observations on southwest Pacific subantarctic islands that lie at the boundary of polar and subtropical climates (52–54˚S). Our annually-resolved temperature reconstruction captures regional change since the 1870s and demonstrates a significant increase in variability from the mid-twentieth century, a phenomenon predating the observational record. Climate reanalysis and modelling shows a parallel change in tropical Pacific sea surface temperatures that generate an atmospheric Rossby wave train which propagates across a large part of the Southern Hemisphere during the austral spring and summer.