Commencement of the Gravity Recovery and Climate Experiment (GRACE) provides an alternative way to monitor changes in terrestrial water storage (TWS) at large scales. However, GRACE data set spans from 2002 to present, which greatly limits the application of GRACE data for long-term hydrological studies. Thus, the general linear model (GLM), random forest (RF), support vector machines (SVM), and artificial neural networks (ANN) methods were used to reconstruct the time series of terrestrial water storage anomalies (TWSA, i.e., remove the average value from the time series) in Northwest China (NWC) during 1948–2002 based on the GRACE TWSA during 2003–2015 and hydrological data from the Global Land Data Assimilation System (GLDAS) during 1948–2010. The results showed that soil moisture (SM) anomalies, or the combination of SM, canopy water (CW), and snow water equivalent (SWE) anomalies were better than the other anomalies of GLDAS in NWC. RF method can be regarded as the optimal method to reconstruct TWSA in NWC in the four models. A negative relationship was found between the reconstructed TWSAs and El Niño-Southern Oscillation (ENSO). The method could also offer an approach to reconstruct TWSA and drought events in large river basins during the past several decades.