Temperate grasslands are globally widespread, play an important role as carbon storage, and harbor unique biodiversity. Livestock grazing is the most widespread land use in temperate grasslands, and understanding the impact of grazing on grassland ecosystems is therefore important. However, monitoring grazing pressure and how it changes is hampered by a lack of adequate tools. The Eurasian steppe belt, extending from Eastern Europe to China has experienced marked changes in grazing pressure. Most notably, livestock numbers in the steppes of Kazakhstan and Russia declined by up to 80% after the breakdown of the Soviet Union in 1991, yet how this impacted spatial patterns of grazing pressure is unclear. To address this research gap, we used all available Landsat data from 1985 to 2017 together with extensive ground reference data on grazing pressure to evaluate a broad range of spectral-temporal metrics regarding their ability to capture grazing pressure. While Tasseled Cap-based disturbance indices performed best, combining all spectral-temporal metrics in a binary random forest classification yielded a grazing class membership probability that strongly outperformed all individual metrics. This new index of grazing pressure correlated well with a range of field-based grazing indicators (e.g., number of dung piles, herbaceous biomass) and yielded highly plausible spatial patterns of grazing pressure. We used this index to reconstruct annual changes in grazing pressure across our 360,000 km2 study region, and used LandTrendr time series segmentation to identify trends in grazing pressure. Aggregated grazing pressure followed closely known trends in total livestock numbers over the time period we studied. The spatial footprint of heavy grazing was very large before 1991, but decreased by 73 (±2) % until 2017. This now leaves large areas virtually ungrazed, even in close vicinity to settlements and agricultural areas, and despite a recent recovery of livestock numbers. Our analyses uncovered previously unknown hot-spots of heavy grazing during Soviet times (e.g., around watering points). Our findings suggest potential for a further revival of the livestock sector as well as for the restoration of steppe ecosystems. More broadly, our study highlights how the Landsat archive, in combination with field data on grazing, can be used to map grazing pressure reliably across large areas and over long time spans.