This article proposes a fundamental methodological shift in the modelling of policy interventions for sustainability transitions in order to account for complexity (e.g. self-reinforcing mechanisms, such as technology lock-ins, arising from multi-agent interactions) and agent heterogeneity (e.g. differences in consumer and investment behaviour arising from income stratification). We first characterise the uncertainty faced by climate policy-makers and its implications for investment decision-makers. We then identify five shortcomings in the equilibrium and optimisation-based approaches most frequently used to inform sustainability policy: (i) their normative, optimisation-based nature, (ii) their unrealistic reliance on the full-rationality of agents, (iii) their inability to account for mutual influences among agents (multi-agent interactions) and capture related self-reinforcing (positive feedback) processes, (iv) their inability to represent multiple solutions and path-dependency, and (v) their inability to properly account for agent heterogeneity. The aim of this article is to introduce an alternative modelling approach based on complexity dynamics and agent heterogeneity, and explore its use in four key areas of sustainability policy, namely (1) technology adoption and diffusion, (2) macroeconomic impacts of low-carbon policies, (3) interactions between the socio-economic system and the natural environment, and (4) the anticipation of policy outcomes. The practical relevance of the proposed methodology is subsequently discussed by reference to four specific applications relating to each of the above areas: the diffusion of transport technology, the impact of low-carbon investment on income and employment, the management of cascading uncertainties, and the cross-sectoral impact of biofuels policies. In conclusion, the article calls for a fundamental methodological shift aligning the modelling of the socio-economic system with that of the climatic system, for a combined and realistic understanding of the impact of sustainability policies.