The largest impact of land-use change on catchment hydrology can be linked to deforestation. This change, driven by exponential population growth, intensified food and industrial production, has resulted in alterations in river flow regimes such as high peaks, reduced base flows, and silt deposition. To reverse this trend more extensive management practices are becoming increasingly important, but can also lead to severe losses in agricultural production. Land-use optimization tools can help catchment managers to explore numerous land-use configurations for the evaluation of trade-offs amongst various uses. In this study, the Soil and water assessment tool (SWAT) model was coupled with a genetic algorithm to identify land-use/management configurations with minimal trade-offs between environmental objectives (reduced sediment load, increased stream low flow) and the crop yields of maize and soybean in Nyangores catchment (Kenya). During the land-use optimization, areas under conventional agriculture could either remain as they are or change to agroforestry or conservation agriculture (CA), where the latter was represented by introducing contour farming and vegetative filter strips. From the sets of the resulting Pareto-optimal solutions we selected mid-range solutions, representing a fair compromise among all objectives, for further analysis. We found that a combined measure implementation strategy (agroforestry on certain sites and conservation agriculture on other sites within the catchment) proved to be superior over single measure implementation strategies. On the catchment scale, a 3.6% change to forests combined with a 35% change to CA resulted in highly reduced sediment loads (−78%), increased low flow (+14%) and only slightly decreased crop yields (<4%). There was a tendency of the genetic algorithm to implement more extensive management practices in the upper part of the catchment while leaving conventional agriculture in the lower part. Our study shows that a spatially targeted implementation strategy for different conservation management practices can remarkably improve environmental sustainability with only marginal trade-offs in crop production at the catchment-level. Incentive policies such as payments for ecosystem services (PES), considering upstream and downstream stakeholders, could offer a practical way to effect these changes.