To address the challenges of water scarcity and the limited accuracy of terrestrial water storage (TWS) estimation in Inner Mongolia, this study integrates GRACE satellite observations, the GLDAS-Noah hydrological model, and ground-based precipitation records, in combination with Theil–Sen median trend analysis and the Mann–Kendall test, to systematically evaluate the spatiotemporal evolution of TWS from 2003 to 2016. The results demonstrate that: (1) GRACE data reliably capture regional water storage dynamics. Over the study period, TWS exhibited a significant overall decline, with an average rate of −5.2 × 10⁻⁴ cm/year, and seasonal variations were strongly coupled with precipitation patterns. (2) Spatially, TWS anomalies (TWSa) decreased from northeast to southwest, with values ranging from approximately +1.22 cm to −2.94 cm. The most pronounced decline was detected in the southern Ordos region. (3) Soil water changes were more substantial than those in canopy or snow water, with sharp reductions occurring during 2004–2007 and 2013–2015. Soil water exhibited clear stratification across different depths, and variations in deep soil water and groundwater were primarily influenced by non-precipitation factors. These findings provide a scientific basis for the sustainable utilization of water resources in Inner Mongolia and yield important insights for regional water management and policy formulation.