One of the most serious threats to the Baltic Sea and its ecosystem services is human-induced eutrophication. European Union legislation, in the form of the Marine Strategy and Water Framework Directives, requires information on the benefits of improving the condition of the sea to a good environmental status. Our study uses a unique dataset collected from all nine littoral countries of the Baltic Sea, in combination with state-of-the-art marine modelling of the area, to estimate the benefits of reducing eutrophication in the Baltic Sea. We find average willingness to pay (WTP) for decreased eutrophication to differ substantially by country, but also that there is a general acceptance to pay more to improve the status of the whole sea area. We estimate the aggregate WTP for an improvement in the eutrophication level following the HELCOM Baltic Sea Action Plan (BSAP) to be 4000 million Euros annually. Our results provide, however, a strong message to the decision makers about the need for ensuring fulfilment of the policy targets in the BSAP. Failure to fulfil the targets would imply foregoing substantial societal benefits.