Implementation of conservation programs are perceived as being crucial for restoring and protecting waters and watersheds from nonpoint source pollution. Success of these programs depends to a great extent on planning tools that can assist the watershed management process. Herein a novel optimization methodology is presented for deriving watershed-scale sediment and nutrient control plans that incorporate multiple, and often conflicting, objectives. The method combines the use of a watershed model (SWAT), representation of best management practices, an economic component, and a genetic algorithm-based spatial search procedure. For two small watersheds in Indiana located in the midwestern portion of the United States, selection and placement of best management practices by optimization was found to be nearly 3 times more cost-effective than targeting strategies for the same level of protection specified in terms of maximum monthly sediment, phosphorus, and nitrogen loads. Conversely, for the same cost, the optimization plan reduced the maximum monthly loads by a factor of 2 when compared to the targeting plan. The optimization methodology developed in this paper can facilitate attaining water quality goals at significantly lower costs than commonly used cost share and targeting strategies.