A target to reduce phosphorus flows into the Gippsland Lakes in south-eastern Australia by 40% in order to improve water quality has previously been established by stakeholders. This target, like many others worldwide, has been set mostly on the basis of environmental concerns, with limited consideration of issues such as technical feasibility, socio-economic constraints, political factors and associated costs and benefits. An integrated analysis at the catchment scale is undertaken to assess the agricultural land management changes required to achieve this target, and to evaluate the cost-effectiveness of these changes. Based on assumptions used, it appears technically feasible to achieve a 40% reduction in P load entering the Lakes. However, the least-costly way of doing so would require around A$1 billion over 25 years, a dramatic increase in the current levels of funding provided for management. Results of a sensitivity analysis indicate that there is little or no chance of investment in a 40% reduction being cost-effective. On the other hand, a 20% P reduction could be achieved at much lower cost: around $80 million over 25 years and requiring more modest land-management changes. Reliance on voluntary adoption of ‘Current Recommended Practices’ is unlikely to deliver changes in management practices at the scale required to have sufficient environmental impacts. Enforcement of existing regulations for the dairy industry would be amongst the most cost-effective management strategies. The major implications of this work for agriculturally induced diffuse-source pollution include the need for feedback between goal setting and program costs, and consideration of factors such as the levels of landholder adoption of new practices that are required and the feasibility of achieving those adoption levels. Costs, landholder adoption of new practices and socio-political risks appear neglected in the formulation of many water quality programs. The study provides a demonstration of an approach to integrated multidisciplinary research addressing complex environmental problems with multiple decision makers, multiple stakeholders, and high uncertainty. On the evidence of experience in this study, the approach deserves consideration in other contexts.