Frozen ground has an important role in regional hydrological cycle and ecosystem, especially on the Qinghai-Tibetan Plateau, which is characterized by high elevation and a dry climate. This study modified a distributed physically-based hydrological model and applied it to simulate the long-term (from 1961 to 2013) change of frozen ground and its effect on hydrology in the upper Heihe basin located at Northeast Qinghai-Tibetan Plateau. The model was validated carefully against data obtained from multiple ground-based observations. The model results showed that the permafrost area shrank by 9.5 % (approximately 600 km2), especially in areas with elevation between 3500 m and 3900 m. The maximum frozen depth of seasonally frozen ground decreased at a rate of approximately 4.1 cm/10 yr, and the active layer depth over the permafrost increased by about 2.2 cm/10 yr. Runoff increased significantly during cold seasons (November–March) due to the increase in liquid soil moisture caused by rising soil temperature. Areas where permafrost changed into the seasonally frozen ground at high elevation showed especially large changes in runoff. Annual runoff increased due to increased precipitation, the base flow increased due to permafrost degradation, and the actual evapotranspiration increased significantly due to increased precipitation and soil warming. The groundwater storage showed an increasing trend, which indicated that the groundwater recharge was enhanced due to the degradation of permafrost in the study area.