Environmental governance regularly has to cope with complex problems. However, ‘complexity’ has mostly been used as a heuristic concept and hardly made operable for empirical research. Drawing on psychological research on complex problem solving, we propose a structured operationalization of complexity in the five dimensions of (1) goals, (2) variables, (3) dynamics, (4) interconnectedness and (5) information uncertainty. Based on 65 semi-standardized expert interviews and 158 assessments of complexity degrees, we analyse and map 37 water-related problems in Germany with regard to their complexity. We find that these problems tend to exhibit medium degrees of complexity, based on 30 types of argument for complexity. Our analysis also reveals varying degrees of complexity and delineates the various natural, technical and social sources of complexity. Our approach and the results may facilitate more systematic discussion of governance strategies for complex problem solving across environmental policy fields and scales.