Centennial- and millennial-scale variability of Southern Ocean temperature over the Holocene is poorly known, due to both short instrumental records and sparsely distributed high-resolution temperature reconstructions, with evidence for past temperature variations in the region coming mainly from ice core records. Here we present a high-resolution (similar to 60 year), diatom-based sea surface temperature (SST) reconstruction from the western Indian sector of the Southern Ocean that spans the interval 14.2 to 1.0 ka (calibrated kiloyears before present). During the late deglaciation, the new SST record shows cool temperatures at 14.2-12.9 ka and gradual warming between 12.9 and 11.6 ka in phase with atmospheric temperature evolution. This supports the evolution of the Southern Ocean SST during the deglaciation being linked with a complex combination of processes and drivers associated with reorganisations of atmospheric and oceanic circulation patterns. Specifically, we suggest that Southern Ocean surface warming coincided, within the dating uncertainties, with the reconstructed slowdown of the Atlantic Meridional Overturning Circulation (AMOC), rising atmospheric CO2 levels, changes in the southern westerly winds and enhanced upwelling. During the Holocene the record shows warm and stable temperatures from 11.6 to 8.7 ka followed by a slight cooling and greater variability from 8.7 to 1 ka, with a quasi-periodic variability of 200-260 years identified by spectral analysis. We suggest that the increased variability during the mid- to late Holocene reflects the establishment of centennial variability in SST connected with changes in the high-latitude atmospheric circulation and Southern Ocean convection.