Increasing attention to regime shifts, critical transitions, non-marginal changes, and systemic shocks calls for the development of models that are able to reproduce or grow structural changes that occur over time periods perceived as abrupt. This paper highlights specific modelling challenges to consider when exploring coupled socio-environmental systems experiencing regime shifts. We explore these challenges in the context of four modelling approaches that have been applied to the study of regime shifts in coupled socio-environmental systems: statistical, system dynamics, equilibrium and agent-based modelling. When reviewing these modelling approaches we reflect on a set of criteria including the ability of an approach (1) to capture feedbacks between social and environmental system, (2) to represent the sources of regime shifts, (3) to incorporate complexity aspects, and (4) to deal with regime shift identification. Many of the modelling examples considered do not provide information on all these criteria, which receive a lot of attention in empirical studies of registered regime shifts. This suggests a need to develop a common modelling terminology in the domain of modelling for resilience and regime shifts. When discussing strengths and weaknesses of various modelling paradigms we conclude that a hybrid approach is likely to provide most insights into the processes and consequences of regime shifts. Challenges and frontier directions of research for designing models to study regime shifts in coupled socio-environmental systems are outlined.