The Yangtze River and the Huang River are the two largest rivers in China. Annual runoff ratios (runoff/precipitation, denoted as RR) of the head regions of these two basins (HYR and HHR, respectively) have significantly decreased over the past several decades, closely related to changes in water storage capacity (WSC) and terrestrial water storage (TWS). However, such effects have rarely been quantified due to limitations associated with complicated arctic hydrological processes and the absence of long-term reliable TWS data. In this study, a TWS reconstruction dataset (TWS_rec) was validated, and demonstrated good performance in capturing TWS variations derived from the Gravity Recovery and Climate Experiment (GRACE) and in the terrestrial water budget for these two head regions. Long-term (1980–2015) changes in TWS and WSC were then detected and their effects on RR were quantified through trend detection, change point analysis, and path analysis. Results showed that TWS increased significantly with a rate of 27.6 mm/10 yr and 19.8 mm/10 yr at HYR and HHR, respectively. These increases were mainly caused by wetting (increases in precipitation) or soil moisture increases from the TWS component perspective. WSC (represented as the ratio of TWS to precipitation) gradually enlarged in response to continuous climate warming. RR decreased significantly with rates of 2.0%/10 yr at HYR and 3.6%/10 yr at HHR, attributed to the increased evaporation ratio (~80%) and increased WSC (~20%) in both head regions. Further analysis suggested that permafrost degradation under climate warming could increase WSC. These results demonstrate that climate change has resulted in unstable terrestrial water storage at HYR and HHR, and that increases in WSC due to permafrost degradation play an important role in accurately simulating runoff in the Tibetan Plateau and other permafrost-degradation regions.