The Gravity Recovery and Climate Experiment (GRACE) mission operated between March 2002 and October 2017, providing monthly global terrestrial water storage anomalies (TWSA), which are essential in investigating global climate change and the hydrological cycle. Its continuation GRACE-Follow On (GRACE-FO) was launched in May 2018, leading to an 11-months data gap between them. Therefore, it is of high significance to fill the data gap. However, existing studies have not yet achieved high prediction accuracy in filling the data gap over Northwest China (NWC). Based on the CSR RL06 spherical harmonics (SH) solution from April 2002 to June 2017, this study combined the Variational Mode Decomposition (VMD) with the Long Short-Term Memory (LSTM) model to fill the data gap over NWC. Two conventional LSTM models were set as control groups: LSTM-1, for which GLDAS-based TWS, temperature, and precipitation were used as input, and LSTM-2, for which TWSA data of the previous 12 months were used as input. In general, the two conventional LSTM models showed poor performance. In contrast, the integrated VMD-LSTM model achieved significantly higher prediction accuracy (NSE = 0.974, CC = 0.989, and RMSE = 0.808 cm) and exhibited higher reliability compared to the single LSTM models. The proposed method offers a means toward bridging the gap in GRACE-based TWSA data over NWC. It also provides a reference for similar regions around the world.