Despite playing a major role in global ocean heat storage, the Southern Ocean remains the most sparsely measured region of the global ocean. Here, a unique 25-year temperature time-series of the upper 800 m, repeated several times a year across the Southern Ocean, allows us to document the long-term change within water-masses and how it compares to the interannual variability. Three regions stand out as having strong trends that dominate over interannual variability: warming of the subantarctic waters (0.29 ± 0.09 °C per decade); cooling of the near-surface subpolar waters (-0.07 ± 0.04 °C per decade); and warming of the subsurface subpolar deep waters (0.04 ± 0.01 °C per decade). Although this subsurface warming of subpolar deep waters is small, it is the most robust long-term trend of our section, being in a region with weak interannual variability. This robust warming is associated with a large shoaling of the maximum temperature core in the subpolar deep water (39 ± 09 m per decade), which has been significantly underestimated by a factor of 3 to 10 in past studies. We find temperature changes of comparable magnitude to those reported in Amundsen-Bellingshausen Seas, which calls for a reconsideration of current ocean changes with important consequences for our understanding of future Antarctic ice-sheet mass loss.