This paper puts forward a framework for probabilistic and holistic cost-effectiveness analysis to provide support in selecting the least-cost set of measures to reach a multidimensional environmental objective. Following the principles of ecosystem-based management, the framework includes a flexible methodology for deriving and populating criteria for effectiveness and costs and analyzing complex ecological-economic trade-offs under uncertainty. The framework is applied in the development of the Finnish Programme of Measures (PoM) for reaching the targets of the EU Marine Strategy Framework Directive (MSFD). The numerical results demonstrate that substantial cost savings can be realized from careful consideration of the costs and multiple effects of management measures. If adopted, the proposed PoM would yield improvements in the state of the Baltic Sea, but the overall objective of the MSFD would not be reached by the target year of 2020; for various environmental and administrative reasons, it would take longer for most measures to take full effect.