Changes in soil nutrient availability attributed to climate change and associated permafrost degradation have been reported in several ecosystems. However, little is known about the changes of soil nutrient availability in alpine grassland ecosystems. Based on a comprehensive dataset and random forest models, we investigated soil available nutrients changes and their relationships with environmental factors for the top 10 cm soils across Tibetan grassland between the 1980s and 2010s. During this period, topsoil available nitrogen stocks increased significantly by 24%, while available phosphorus and potassium stocks decreased significantly by 3% and 23%, respectively. Topsoil nutrient availability dynamics varied substantially among vegetation types. Initial nutrient stocks explained the largest proportions of available nutrients changes, though climate, permafrost, vegetation, soil properties, and their interactions also had significant contributions. The increasing rate of active layer thickness was negatively related to soil available nitrogen dynamics but did not significantly change available phosphorus and potassium, indicating that the increase in the annual depth of surface thaw of the permafrost was associated with an increase in soil nitrogen availability but no significant changes in available phosphorus and potassium. These results suggest that the Tibetan alpine grassland ecosystems may shift from nitrogen limited to phosphorus or potassium-limited in the future.