Governance for complex problem solving has been increasingly discussed in environmental sustainability research. Above all, researchers continuously observe that sustainability problems are complex or “wicked”, and suggest participatory models to address these problems in practice. In order to add to this debate, this study suggests a more differentiated theoretical approach to define governance for complex environmental problem solving than in previous studies. The approach consists of two vital steps: First, we operationalize complexity and define management strategies for solving environmental sustainability problems based on findings from psychology research. Second, we identify governance strategies that facilitate these management strategies. Linking those strategies suggests that the role of diverse institutions, actors, and interactions differs for five key dimensions of complexity: goals, variables, dynamics, interconnections, and informational uncertainty. The results strengthen systematic analyses of environmental sustainability problems in both theory and practice.