Nature-based Solutions (NbS) are promoted as effective strategies to address agricultural land degradation and advance Land Degradation Neutrality (LDN). However, identifying context-appropriate NbS remains challenging due to socio-ecological trade-offs and diverse stakeholder priorities. This study empirically tests an integrated Multi-Criteria Decision Analysis (MCDA) and Social Choice Theory (SCT) framework for participatory NbS prioritisation. Data were collected through a multi-stakeholder workshop in northern Tanzania involving 31 purposively sampled participants across four stakeholder groups: farmers/agropastoralists, NGOs, local authorities, and agricultural professionals. Descriptive analysis was used to examine how stakeholder groups prioritised NbS decision criteria. NbS alternatives were evaluated using the Weighted Sum Model within MCDA, combined with SCT’s k-approval method, to identify the three most context-appropriate options. Participatory and expert-driven outcomes were compared using correlation and rank-agreement analysis, and robustness was assessed through scenario-based sensitivity analysis. Results show broad stakeholder consensus in prioritising environmental restoration functions of NbS, particularly soil erosion control, alongside stakeholder-specific differences in the prioritisation of other criteria. The integrated framework identified contour planting, cover cropping, and agroforestry as the highest-ranked NbS options. Incorporating SCT altered the final ordering of alternatives, demonstrating its influence on decision outcomes. Findings further showed that participatory and expert-driven outcomes diverged, indicating that stakeholder inclusion can materially influence prioritisation outcomes, beyond procedural benefits. Sensitivity analysis confirmed that rankings were robust under varying weighting scenarios. Overall, the study advances NbS and LDN research by demonstrating how participatory decision-support frameworks can support the selection of context‑appropriate and socially legitimate NbS to advance LDN.