Hydro-meteorological risks are a growing issue for societies, economies and environments around the world. An effective, sustainable response to such risks and their future uncertainty requires a paradigm shift in our research and practical efforts. In this respect, Nature-Based Solutions (NBSs) offer the potential to achieve a more effective and flexible response to hydro-meteorological risks while also enhancing human well-being and biodiversity. The present paper describes a new methodology that incorporates stakeholders’ preferences into a multi-criteria analysis framework, as part of a tool for selecting risk mitigation measures. The methodology has been applied to Tamnava river basin in Serbia and Nangang river basin in Taiwan within the EC-funded RECONECT project. The results highlight the importance of involving stakeholders in the early stages of projects in order to achieve successful implementation of NBSs. The methodology can assist decision-makers in formulating desirable benefits and co-benefits and can enable a systematic and transparent NBSs planning process.