A nutrient reduction strategy for Iowa identifies land use and conservation alternatives to reduce nutrient loss from agriculture and the resulting Gulf of Mexico hypoxia. From the viewpoint of a policy maker concerned with regional costs and benefits, we develop a land use optimization model to maximize profit while satisfying nutrient reduction constraints. Because uncertain precipitation levels affect both yields and nutrient loss, we formulate two variants of a multistage stochastic mixed-integer program with probabilistic scenarios for annual precipitation generated from a Markov chain model. Numerical sensitivity analyses on the recourse variant reveal complicated interactions among the nutrient reduction and labor availability constraints as well as crop prices. The chance-constrained variant provides needed flexibility in meeting nutrient reduction goals by neglecting low-probability precipitation outcomes. Case study results indicate that, although significant financial incentives might be required for landowners to implement optimal strategies, substantial reductions in nutrient loss can be achieved.