We use a recent reconstruction of global mean sea surface temperature change relative to preindustrial (ΔGMSST) over the last 4.5 Myr together with independent proxy-based reconstructions of bottom water (ΔBWT) or deep-ocean (ΔDOT) temperatures to infer changes in mean ocean temperature (ΔMOT). Three independent lines of evidence show that the ratio of ΔMOT / ΔGMSST​​​​​​​, which is a measure of ocean heat storage efficiency (HSE), increased from ∼ 0.5 to ∼ 1 during the Middle Pleistocene Transition (MPT, 1.5–0.9 Ma), indicating an increase in ocean heat uptake (OHU) at this time. The first line of evidence comes from global climate models; the second from proxy-based reconstructions of ΔBWT, ΔMOT, and ΔGMSST; and the third from decomposing a global mean benthic δ18O stack (δ18Ob) into its temperature (δ18OT) and seawater (δ18Osw) components. Regarding the latter, we also find that further corrections in benthic δ18O, probably due to some combination of a long-term diagenetic overprint and to the carbonate ion effect, are necessary to explain reconstructed Pliocene sea-level highstands inferred from δ18Osw. We develop a simple conceptual model that invokes an increase in OHU and HSE during the MPT in response to changes in deep-ocean circulation driven largely by surface forcing of the Southern Ocean. Our model accounts for heat uptake and temperature in the non-polar upper ocean (0–2000 m) that is mainly due to wind-driven ventilation, while changes in the deeper ocean (> 2000 m) in both polar and non-polar waters occur due to high-latitude deepwater formation. We propose that deepwater formation was substantially reduced prior to the MPT, effectively decreasing HSE. We attribute these changes in deepwater formation across the MPT to long-term cooling which caused a change starting ∼ 1.5 Ma from a highly stratified Southern Ocean due to warm SSTs and reduced sea-ice extent to a Southern Ocean which, due to colder SSTs and increased sea-ice extent, had a greater vertical exchange of water masses.