Problem complexity is often assumed to hamper effective environmental policy delivery. However, this claim is hardly substantiated, given the dominance of qualitative small-n designs in environmental governance research. We studied 37 types of contemporary problems defined by German water governance to assess the impact of problem complexity on policy delivery through public authorities. The analysis is based on a unique data set related to these problems, encompassing both in-depth interview-based data on complexities and independent official data on policy delivery. Our findings show that complexity in fact tends to delay implementation at the stage of planning. However, different dimensions of complexity (goals, variables, dynamics, interconnections, and uncertainty) impact on the different stages of policy delivery (goal formulation, stages and degrees of implementation) in various ways.