Nitrogen leakage from agriculture contributes significantly to eutrophication of freshwater and marine ecosystems, and numerous studies have focused on finding cost-effective ways to mitigate this effect. This article utilizes high-resolution data to identify a spatially targeted cost-effective reduction of nitrogen leakage, optimizing over measures as well as over locations. The use of discrete optimization techniques ensure that mutually exclusive measures are not applied on the same plot of land. The analysis is based on a case study of Odense Fjord, where spatially explicit data capture the spatial heterogeneity of the effects and costs of abatement measures. The differences in retention capacity; soil types; and current land use are particularly important factors for the spatial variation in costs and effects. The analysis highlights the importance of applying discrete optimization techniques in spatially specific analyses. We find that no unambiguous ranking of measures or spatial pattern of abatement effort can be given. Hence, landscape scale models are needed to identify optimal abatement effort. The results show that spatial targeting offers substantial improvements in cost-effectiveness compared to a uniform regulation.