Ecosystem and associated services in arid and semiarid areas are sensitive to climate change and human activities. Guiding human activities based on the optimization of ecosystem services can help humans adapt to climate change effectively, which is vital for regional sustainability. We evaluated the distribution of five ecosystem services: net primary productivity (NPP), soil conservation (SC), water yield (WY), water retention (WR), and livestock supply in the grassland and agro-pastoral transitional zone of China (GAPTZ) under the future climate scenarios of representative concentration pathway (RCP) 4.5 and RCP8.5 in 2050. We designed the four grazing-intensity scenarios of ungrazed (UG), lightly grazed (LG), moderately grazed (MG), and heavily grazed (HG) and analyzed the impacts of climate change and grazing on the ecosystem services. Finally, we presented the optimization schemes of grazing intensity in the GAPTZ under the objectives of “strong sustainability” and “weak sustainability”. “Strong sustainability” objective means that the total change rate of ecosystem services compared to the ungrazed scenario is maximal and should not be less than 0. “Weak sustainability” objective means that the livestock supply is preferential and the total change rate of ecosystem services compared to the ungrazed scenario is maximal but could be less than 0. The results showed that both climate change and grazing exert great influence on the supply and interrelation of ecosystem services. In the northeast of the GAPTZ, LG and MG can stimulate grassland to tiller and enlarge ecosystem services integrally. HG has the severest negative effect on ecosystem services overall. Under the “weak sustainability” objective, LG can be widely adopted in the GAPTZ. Under the “strong sustainability” objective, grazing should be limited in the northwestern and north-central GAPTZ. Reasonable planning of grazing intensity and its spatial patterns can promote effective utilization of grassland resource and realization of regional sustainability.