As the major sink of anthropogenic heat, the Southern Ocean has shown quasi-symmetric, deep-reaching warming since the mid-20^th century. In comparison, the shorter-term heat storage pattern of the Southern Ocean is more complex and has notable impacts on regional climate and marine ecosystems. By analyzing observational datasets and climate model simulations, this study reveals that the Southern Ocean exhibits prominent decadal (> 8 years) variability extending to ~700 m depth and is characterized by out-of-phase changes in the Pacific and Atlantic-Indian Ocean sectors. Changes in the Pacific sector are larger in magnitude than those in the Atlantic-Indian Ocean sectors and dominate the total heat storage of the Southern Ocean on decadal timescales. Instead of heat uptake through surface heat fluxes, these asymmetric variations arise primarily from wind-driven heat redistribution. Pacemaker and pre-industrial simulations of the Community Earth System Model version-1 (CESM1) suggest that these variations in Southern Ocean winds arise primarily from natural variability of the tropical Pacific, as represented by the Interdecadal Pacific Oscillation (IPO). Through atmospheric teleconnection, the positive phase of the IPO gives rise to higher-than-normal sea-level pressure and anti-cyclonic wind anomalies in the 50°-70°S band of the Pacific sector. These winds lead to warming of 0-700 m by driving the convergence of warm water. The opposite processes, involving cyclonic winds and upper-layer divergence, occur in the Atlantic-Indian Ocean sector. These findings aid our understanding of the time-varying heat storage of the Southern Ocean and provide useful implications on initialized decadal climate prediction.