Climate models show the possibility of abrupt climate changes caused by a collapse of the North Atlantic thermohaline circulation (THC). Strong THC fluctuations on interannual to interdecadal timescales and high erros in THC measurements hinder the detection of a possible THC slowdown.Our analysis shows that the temperature structure in the Atlantic Ocean can be a sensitive indicator identifying early THC weakening with a high signal-to-noise ratio. Simulations with the coupled atmosphere-ocean circulation model ECHAM5/MPI-OM emphasize the subsurface temperature signature in the Atlantic Ocean with its potential to trace THC changes. A part of this signature can be understood with the advective-diffusive balance which is confirmed in a stochastic low-order model of the Atlantic Ocean circulation. Finally, instrumental and proxy data are used to estimate THC fluctuations on decadal to multi-decadal time scales.