Payment schemes for ecosystem services such as Reducing Emissions from Deforestation and forest Degradation (REDD) rely on the prediction of ‘business-as-usual’ scenarios to ensure that emission reductions from carbon credits are additional. However, land systems often undergo periods of nonlinear and abrupt change that invalidate predictions calibrated on past trends. Rapid land-system change can occur when critical thresholds in broad-scale underlying drivers such as commodity prices and climate conditions are crossed or when sudden events such as political change or natural disasters punctuate long-term equilibria. As a result, land systems can shift to new regimes with markedly different economic and ecological characteristics. Anticipating the timing and nature of regime shifts of land systems is extremely challenging, as we demonstrate through empirical case studies in four countries in Southeast Asia (China, Laos, Vietnam and Indonesia). The results show how sudden events and gradual changes in underlying drivers caused rapid, surprising and widespread land-system changes, including shifts to different regimes in China, Vietnam and Indonesia, whereas land systems in Laos remained stable in the study period but show recent signs of rapid change. The observed regime shifts were difficult to anticipate, which compromises the validity of predictions of future land-system changes and the assessment of their impact on greenhouse gas emissions, hydrological processes, agriculture, biodiversity and livelihoods. This implies that long-term initiatives such as REDD must account for the substantial uncertainties inherent in future predictions of land-system change. Learning from past regime shifts and identifying early warning signs for future regime shifts are important challenges for land-system science.