Terrestrial water storage (TWS) is a critical variable in the global hydrological cycle. The TWS estimates derived from the Gravity Recovery and Climate Experiment (GRACE) allow us to better understand water exchanges between the atmosphere, land surface, sea, and glaciers. However, missing historical (pre-2002) GRACE data limit their further application. In this study, we developed a random forest (RF) model to reconstruct the monthly terrestrial water storage anomaly (TWSA) time series using Global Land Data Assimilation System (GLDAS) and Climatic Research Unit (CRU) data for the Lancang-Mekong River basin. The results show that the RF-built TWSA time series agrees well with the GRACE TWSA time series for 2003–2014, showing that correlation coefficients (R) of 0.97 and 0.90 at the basin and grid scales, respectively, which demonstrates the reliability of the RF model. Furthermore, this method is used to reconstruct the historical TWSA time series for 1980–2002. Moreover, the discharge can be obtained by subtracting the evapotranspiration (ET) and RF-built terrestrial water storage change (TWSC) from the precipitation. The comparison between the discharge calculated from the water balance method and the observed discharge showed significant consistency, with a correlation coefficient of 0.89 for 2003–2014 but a slightly lower correlation coefficient (0.86) for 1980–2002. The methods and findings in this study can provide an effective means of reconstructing the TWSA and discharge time series in basins with sparse hydrological data.