Policy efforts to improve Baltic Sea water quality will be expensive if the ambitious targets agreed are to be achieved. The aim of this study is to evaluate the ex-post cost-effectiveness of nitrogen load reductions to the Baltic Sea made between 1996 and 2010. We first calculate the counterfactual change in nitrogen load to the Baltic Sea and compare to observed loads. The costs of the net reductions are evaluated using a Baltic-wide cost-effectiveness model, which includes a wide set of nitrogen abatement measures in the littoral countries. Results show that the net nitrogen reductions achieved through environmental policy, about 145,000 tons total nitrogen, could have been obtained at 12% of the realized cost, through reallocation of abatement between countries. The total budget spent on abatement could, if used in a cost-effective manner, be sufficient for a doubling of the net nitrogen load reduction. Milestone targets, in combination with a compensation scheme between countries, could help to reduce policy costs.