Strategies to reduce phosphorus and sediment yields are identified for two Australian catchments using a nonlinear optimisation model. This provides novel insight into the cost-effective management of dual pollutants of water courses in Australia. A strong degree of complementarity between the two pollutants is highlighted, given the adsorption of phosphorus to sediment that augments the value of gully and streambank management for mitigation. However, the relationship between the two pollutants is asymmetric. A 30 per cent reduction in phosphorus yield achieves a 75 per cent reduction in sediment yield in one catchment, while a 30 per cent reduction in sediment yield achieves only a 12 per cent reduction in phosphorus yield. Sediment abatement costs are low given the efficiency of gully and streambank management. A 30 per cent phosphorus reduction lowers profit by 3–7 per cent, while a 30 per cent sediment reduction lowers profit by around 1 per cent. Land-use optimisation requires spatial heterogeneity in land-use and gully/streambank management responses. Overall, this research demonstrates the need to determine whether one pollutant is more important than another, while recognising the potential that mitigation practices possess for the reduction of multiple emissions during their evaluation.