Agent-based models (ABMs) are increasingly recognized as valuable tools in modelling human-environmental systems, but challenges and critics remain. One pressing challenge in the era of “Big Data” and given the flexibility of representation afforded by ABMs, is identifying the appropriate level of complicatedness in model structure for representing and investigating complex real-world systems. In this paper, we differentiate the concepts of complexity (model behaviour) and complicatedness (model structure), and illustrate the non-linear relationship between them. We then systematically evaluate the trade-offs between simple (often theoretical) models and complicated (often empirically-grounded) models. We propose using pattern-oriented modelling, stepwise approaches, and modular design to guide modellers in reaching an appropriate level of model complicatedness. While ABMs should be constructed as simple as possible but as complicated as necessary to address the predefined research questions, we also warn modellers of the pitfalls and risks of building “mid-level” models mixing stylized and empirical components.