Sustainable management of contaminated sediments requires careful prioritization of available resources and focuses on efforts to optimize decisions that consider environmental, economic, and societal aspects simultaneously. This may be achieved by combining different analytical approaches such as risk analysis (RA), life cycle analysis (LCA), multicriteria decision analysis (MCDA), and economic valuation methods. We propose the use of stochastic MCDA based on outranking algorithms to implement integrative sustainability strategies for sediment management. In this paper we use the method to select the best sediment management alternatives for the dibenzo-p-dioxin and -furan (PCDD/F) contaminated Grenland fjord in Norway. In the analysis, the benefits of health risk reductions and socio-economic benefits from removing seafood health advisories are evaluated against the detriments of remedial costs and life cycle environmental impacts. A value-plural based weighing of criteria is compared to criteria weights mimicking traditional cost-effectiveness (CEA) and cost-benefit (CBA) analyses. Capping highly contaminated areas in the inner or outer fjord is identified as the most preferable remediation alternative under all criteria schemes and the results are confirmed by a probabilistic sensitivity analysis. The proposed methodology can serve as a flexible framework for future decision support and can be a step toward more sustainable decision making for contaminated sediment management. It may be applicable to the broader field of ecosystem restoration for trade-off analysis between ecosystem services and restoration costs.