In Indonesia, land cover change for agriculture and mining is threatening tropical forests, biodiversity and ecosystem services. However, land cover change is highly dynamic and complex and varies over time and space. In this study, we combined Landsat-based land cover (change) mapping, pixel-to-pixel cross tabulations and expert knowledge to analyze land cover change and forest loss in the West Kutai and Mahakam Ulu districts in East Kalimantan from 1990–2009. We found that about one-third of the study area changed in 1990–2009 and that the different types of land cover changes in the study area increased and involved more diverse and characteristic trajectories in 2000–2009, compared to 1990–2000. Degradation to more open forest types was dominant, and forest was mostly lost due to trajectories that involved deforestation to grasslands and shrubs (~17%), and to a lesser extent due to trajectories from forest to mining and agriculture (11%). Trajectories from forest to small-scale mixed cropland and smallholder rubber occurred more frequently than trajectories to large-scale oil palm or pulpwood plantations; however, the latter increased over time. About 11% of total land cover change involved multiple-step trajectories and thus “intermediate” land cover types. The combined trajectory analysis in this paper thus contributes to a more comprehensive analysis of land cover change and the drivers of forest loss, which is essential to improve future land cover projections and to support spatial planning.