Frozen ground has an important role in regional hydrological cycles and ecosystems, particularly on the Qinghai–Tibetan Plateau (QTP), which is characterized by high elevations and a dry climate. This study modified a distributed, physically based hydrological model and applied it to simulate long-term (1971–2013) changes in frozen ground its the effects on hydrology in the upper Heihe basin, northeastern QTP. The model was validated against data obtained from multiple ground-based observations. Based on model simulations, we analyzed spatio-temporal changes in frozen soils and their effects on hydrology. Our results show that the area with permafrost shrank by 8.8 % (approximately 500 km2), predominantly in areas with elevations between 3500 and 3900 m. The maximum depth of seasonally frozen ground decreased at a rate of approximately 0.032 m decade−1, and the active layer thickness over the permafrost increased by approximately 0.043 m decade−1. Runoff increased significantly during the cold season (November–March) due to an increase in liquid soil moisture caused by rising soil temperatures. Areas in which permafrost changed into seasonally frozen ground at high elevations showed especially large increases in runoff. Annual runoff increased due to increased precipitation, the base flow increased due to changes in frozen soils, and the actual evapotranspiration increased significantly due to increased precipitation and soil warming. The groundwater storage showed an increasing trend, indicating that a reduction in permafrost extent enhanced the groundwater recharge.