Spatially explicit reconstruction of historical grassland cover can provide significant data for studies on the global and regional environmental change. However, being subject to the attribute of study objective and materials for reconstruction, progresses were rarely made both in the estimates of grassland area and the reconstruction of spatial patterns. Based on a good understanding of the grassland change history across western China, we attempted to determine the potential distribution extent of grassland cover without land reclamation using remote sensing-derived land use data and potential vegetation data. Then by overlaying Chinese historical cropland data over a map of the potential distribution extent of grassland vegetation, we proposed a reconstruction method of historical grassland cover across western China. Subsequently, as a case study, grassland cover maps in Gansu, Ningxia, Qinghai, and Xinjiang provinces during AD 1661 to AD 1980 were complied using this approach. The results show that: (1) the grassland coverage across the case area was 40.87% without land reclamation. However, due to the expansion of land reclamation, the amount of grassland decreased continuously, especially over the past 300 years. (2) The total area of grassland across this region decreased from 110.86 million ha in 1661 to 103.14 million ha in 1980. And changes in grassland area went through three phases over this study period, including a sharp decrease between 1661 and 1724, a slow decrease between 1724 and 1873, and a rapid decrease between 1873 and 1980. The average annual losses of grassland area in the three stages were 47.6 thousand ha, 7.5 thousand ha, and 33.8 thousand ha, respectively. Spatially, the main areas of grassland reclamation gradually transferred from Gansu and Ningxia to Qinghai and Xinjiang during the study period. (3) Based on historical archives and remote sensing-derived grassland data in 1980, we evaluated the reliability of the reconstructed grassland cover. Evaluations suggest that the reconstruction results captured the amounts and spatial distribution patterns of historical grassland cover well. Our methods can be used for the long-term reconstruction of grassland cover across western China.