The effectiveness of conservation practices depends on their placement on the fields within the watershed. Cost-effective placement of these practices for maximum water quality benefits on each field requires comparing a very large number of possible land-use scenarios. To address this problem, we combine the tools of evolutionary algorithm with the Soil and Water Assessment Tool (SWAT) model and cost data to develop a trade-off frontier of least cost of achieving nutrient reductions and the corresponding locations of conservation practices. This approach was applied to the Raccoon River Watershed, which drains about 9,400 km2 of an intensive agriculture region in west-central Iowa. Applying genetic algorithm to the calibrated SWAT modeling setup produced multitudes of optimal solutions of achieving nutrient reductions in relation to the total cost of placing these practices. For example, a 30% reduction in nitrate (and a corresponding 53% reduction in phosphorus) at the watershed outlet can be achieved with a cost of $80 million per year. This solution frontier allows policymakers and stakeholders to explicitly see the trade-offs between cost and nutrient reductions.