A target to reduce phosphorus flows into the Gippsland Lakes in south-eastern Australia by 40 per cent to improve water quality has previously been established by stakeholders. 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. It appears technically feasible to achieve a 40 per cent reduction in P load entering the lakes, but the least-costly way of doing so would require around A$1 billion over 20 years, a dramatic increase in the current levels of funding provided for management. On the other hand, a 20 per cent P reduction could be achieved at much lower cost: around $80 million over 20 years and requiring more modest land-management changes. The choice of optimal land-management strategies depends upon whether on-going costs for management maintenance are likely to be available after the initial funding ceased. Reliance on voluntary adoption of ‘Current Recommended Practices’ (CRPs) 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, land holder adoption of new practices and socio-political risks appear neglected in the formulation of many water quality programs. The framework used in this study provides a strong basis for discussion and debate about the environmental outcomes that can be achieved with limited budgets and also about the agricultural production and environmental tradeoffs required to reduce diffuse-source nutrient pollution. The results are relevant to comparable water-quality programs worldwide.