In 2008, the hypoxic zone in the Gulf of Mexico, measuring 20 720 km2, was one of the two largest reported since measurement of the zone began in 1985. The extent of the hypoxic zone is related to nitrogen and phosphorous loadings originating on agricultural fields in the upper Midwest. This study combines the tools of evolutionary computation with a water quality model and cost data to develop a trade-off frontier for the Upper Mississippi River Basin specifying the least cost of achieving nutrient reductions and the location of the agricultural conservation practices needed. The frontier allows policymakers and stakeholders to explicitly see the trade-offs between cost and nutrient reductions. For example, the cost of reducing annual nitrate-N loadings by 30% is estimated to be US$1.4 billion/year, with a concomitant 36% reduction in P and the cost of reducing annual P loadings by 30% is estimated to be US$370 million/year, with a concomitant 9% reduction in nitrate-N.