Lakes are widely distributed on the Mongolian Plateau and, as critical water sources, have sustained Mongolian pastures for hundreds of years. However, the plateau has experienced significant lake shrinkage and grassland degradation during the past several decades. To quantify the changes in all of the lakes on the plateau and the associated driving factors, we performed a satellite-based survey using multitemporal Landsat images from the 1970s to 2000s, combined with ground-based censuses. Our results document a rapid loss of lakes on the plateau in the past decades: the number of lakes with a water surface area >1 km2 decreased from 785 in the late 1980s to 577 in 2010, with a greater rate of decrease (34.0%) in Inner Mongolia of China than in Mongolia (17.6%). This decrease has been particularly pronounced since the late 1990s in Inner Mongolia and the number of lakes >10 km2 has declined by 30.0%. The statistical analyses suggested that in Mongolia precipitation was the dominant driver for the lake changes, and in Inner Mongolia coal mining was most important in its grassland area and irrigation was the leading factor in its cultivated area. The deterioration of lakes is expected to continue in the following decades not only because of changing climate but also increasing exploitation of underground mineral and groundwater resources on the plateau. To protect grasslands and the indigenous nomads, effective action is urgently required to save these valuable lakes from further deterioration.