The growing interest in integrating climate change considerations into Programmes of Measures (PoMs) under the EU Water Framework Directive (WFD) is being driven in part by the requirements of the next generation of River Basin Management Plans (RBMPs). However, so far most studies have focused on potential impacts of climate change on water bodies and the adaptation to climate change-related risks, whereas the relationship between RBMP's and mitigation of climate change – through the reduction in emissions of greenhouse gasses (GHG) – has only been touched upon. This paper investigates the potential for synergies between reduction of nutrient losses from agriculture and climate change mitigation in a case study of the Isefjord and Roskilde Fjord River Basin in Denmark. For this purpose, a map-based approach is applied to analyze the effects and cost-effectiveness of selected PoMs to reduce both nitrogen loads and GHG emissions from agriculture at the river basin scale. The results indicate a substantial potential for cost-effective integration of climate change mitigation into WFD action programmes with special emphasis on four agri-environmental N-GHG measures applied in combination: (1) manure treatment for biogas production and improved N utilization, (2) cultivation of perennial energy crops, (3) extensification of intensively farmed lowland areas and (4) wetland restoration. The particular PoMs investigated can ensure fulfilment of the WFD GES objectives for Isefjord and Roskilde Fjord in a cost-effective way and at the same time reduce GHG emissions significantly, corresponding to a 35–65% reduction of total agricultural GHG emissions within the river basin. This study suggests that a targeted and differentiated approach to the development of PoMs is necessary in order to attain the full potential of these kinds of win–win solutions in the context of the WFD.