Aquatic ecosystems are increasingly impacted by human activities which have lowered their resilience. Despite growing awareness of the need to invest in nature-positive remediation projects, holistic plans that optimize investment and achieve multiple benefits for the least cost are still lacking. The Building Catchment Resilience (BCR) Project (https://www.catchmentresilience.org/) is an innovative decision support tool for planning river and catchment rehabilitation in a cost-effective manner. It includes a Multi-Objective Simulated Annealing (MOSA) model to quantify the effects of different catchment rehabilitation measures. The BCR model has been successfully trialled in a pilot catchment, Laidley creek, South-East Queensland. A user interface was also developed to provide a realistic visual representation of selected solutions from MOSA and facilitate discussions with investors, catchment managers, and the broader community. Two investment scenarios: one aimed at optimizing sediment and nitrogen loss for a fixed implementation cost of $20 million, and the other aimed at halving particulate nitrogen loads, were chosen to demonstrate the utility of the model. The framework was found to be effective and efficient in analyzing the management actions at each location in the catchment, to reduce the sediment and nutrients, and provide estimates of opportunity and implementation costs. The user interface also provides a virtual overview that allows stakeholders to explore and understand trade-offs between key objectives (sediment, nutrients, and costs) and synergies based on their priorities. Moreover, the selected optimal solutions can be further analyzed using a ‘rain-on-grid’ catchment model for flood risk assessment to quantify additional catchment-scale benefits.