River barriers can disrupt connectivity, sediment transport, water flow, and biodiversity, leading to widespread degradation of river ecosystems. Hence, the EU Nature Restoration Law (NRL) urges river connectivity restoration by removing barriers. However, its implementation requires robust, data-driven prioritization strategies. In this study, we apply a multi-scenario spatial optimization framework using multi-criteria decision analysis to prioritize barrier removal across seven conservation scenarios—focusing on biodiversity enhancement, erosion reduction, and human impact mitigation—within the Morava sub-basin of the Danube Basin. Our findings reveal substantial variability in prioritization across scenarios, driven by differing costs. At the same time, certain areas consistently emerge as high priority, indicating their role in improving connectivity and riparian restoration. Removing barriers in these areas could restore up to 1011 km of free-flowing river length and 604 ha of riparian zones. These results provide actionable insights for identifying areas that maximize ecological benefits while minimizing socio-economic trade-offs, supporting effective restoration planning. Despite the utility of this approach, challenges remain, particularly the lack of high-resolution data for small and undocumented barriers and the exclusion of smaller streams. Expanding this analysis to basin-wide scales and incorporating detailed datasets—such as sediment dynamics and climate change scenarios—will refine future outcomes. Additionally, transboundary coordination will be essential to achieve the NRL’s target of 25,000 km of free-flowing rivers. This study highlights the trade-offs between ecological restoration and socio-economic constraints, demonstrating how scenario-based spatial optimization provides a structured framework for balancing these priorities.