Proxy reconstructions suggest that increasing global mean sea surface temperature (GMSST) during the last deglaciation was accompanied by a comparable or greater increase in global mean ocean temperature (GMOT), corresponding to a large heat storage efficiency (HSE; ∆GMOT/∆GMSST). An increased GMOT is commonly attributed to surface warming at sites of deepwater formation, but winter sea ice covered much of these source areas during the last deglaciation, which would imply an HSE much less than 1. Here, we use climate model simulations and proxy-based reconstructions of ocean temperature changes to show that an increased deglacial HSE is achieved by warming of intermediate-depth waters forced by mid-latitude surface warming in response to greenhouse gas and ice sheet forcing as well as by reduced Atlantic meridional overturning circulation associated with meltwater forcing. These results, which highlight the role of surface warming and oceanic circulation changes, have implications for our understanding of long-term ocean heat storage change.