Achieving a good ecological status in water bodies by 2015 is one of the objectives established in the European Water Framework Directive. Cost-effective analysis (CEA) has been applied for selecting measures to achieve this goal, but this appraisal technique requires technical and economic information that is not always available. In addition, there are often local insights that can only be identified by engaging multiple stakeholders in a participatory process. This paper proposes to combine CEA with the active involvement of stakeholders for selecting cost-effective measures. This approach has been applied to the case study of one of the main coastal lagoons in the European Mediterranean Sea, the Mar Menor, which presents eutrophication problems. Firstly, face-to-face interviews were conducted to estimate relative effectiveness and relative impacts of a set of measures by means of the pairwise comparison technique. Secondly, relative effectiveness was used to estimate cost-effectiveness ratios. The most cost-effective measures were the restoration of watercourses that drain into the lagoon and the treatment of polluted groundwater. Although in general the stakeholders approved the former, most of them stated that the latter involved some uncertainties, which must be addressed before implementing it. Stakeholders pointed out that the PoM would have a positive impact not only on water quality, but also on fishing, agriculture and tourism in the area. This approach can be useful to evaluate other programmes, plans or projects related to other European environmental strategies.