During the past decades, overuse of land resources has increasingly contributed to environmental crises in China. To mitigate wide-spread land degradation, actions have been taken to maintain and restore ecologically valuable landscapes such as natural forests. However, the effects of the various vegetation protection policies that have been implemented in China since the late 1990′s still remain largely unknown. In this paper, we therefore focus on mapping land use and land cover change (LULCC) in Inner Mongolia, one of the key regions targeted by Chinese ecological restoration programs. We used 250-m MODIS time series and a random forest classification approach to generate annual probabilities for each land cover class between 2000 and 2014. We then applied a trajectory-based change detection approach based on a modified version of the Landsat-based detection of trends in disturbance and recovery (LandTrendr) algorithm to the probability time series and mapped land cover change trajectories. We found that our trajectory-based approach achieved high accuracies (overall accuracy 0.95±0.02). It provides spatial-temporal land change maps that allow a land-use related interpretation of change patterns. Our change maps show that i) forest loss decreased rapidly after 2000 (from 15,717±1770ha in 2001 to 1313±165ha in 2014) and forest gain (190,645±28,352ha during 2001-2014) occurred in the ecological program zones, leading to a net forest increase in Inner Mongolia, and ii) cropland retirement (212,979±54,939ha during 2001-2014) mostly occurred at the early stage of ecological programs and mainly concentrated in drier environments and steep terrain. Overall, land cover mapping and trajectory-based land use analyses allowed a consistent characterization of LULCC over large areas, which is crucial for gaining a better understanding of environmental changes in the light of rapidly changing environmental policies and governance regimes in China.