Excess loading of nitrogen and phosphorus to river networks causes environmental harm, but reducing loads from large river basins is difficult and expensive. We developed a new tool, the River Basin Export Reduction Optimization Support Tool (RBEROST) to identify the least-cost combinations of management practices that will reduce nutrient loading to target levels in downstream and mid-network waterbodies. We demonstrate the utility of the tool in a case study in the Upper Connecticut River Basin in New England, USA. The total project cost of optimized lowest-cost plans ranged from $18.0 million to $41.0 million per year over 15 years depending on user specifications. Plans include both point source and non-point source management practices, and most costs are associated with urban stormwater practices. Adding a 2% margin of safety to loading targets improved the estimated probability of success from 37.5% to 99%. The large spatial scale of RBEROST, and the consideration of both point and non-point source contributions of nutrients, make it well suited as an initial screening tool in watershed planning.