Nature-based Solutions (NbS) offer significant potential to address climate change while promoting sustainable development. However, their long-term success is often hindered by organisational, financial, and knowledge-related challenges, with collaboration emerging as a critical yet complex factor. While collaboration facilitates stakeholder engagement and enhances NbS implementation, it also introduces barriers, such as conflicting interests, institutional rigidity, and resource constraints, that can undermine project outcomes. This paper proposes a methodological framework that can potentially facilitate collaborative processes for the implementation of NbS. Departing from a systematic analysis of documental evidence available for the implementation of 11 NbS projects within the Horizon 2020 framework, the research identifies recurring collaboration challenges and suggests potential tools to address them. The proposed tools are inspired by the principles of Service Design, a multidisciplinary field merging behavioural sciences, technology, and design proven to have created both tangible and intangible elements for design solutions. The proposed tools utilise hybrid perspectives, combining traditional methodological approaches and innovative instruments, including technology and artificial intelligence instruments. The findings highlight diverse forms of collaboration, such as co-design and co-governance, driven by the involvement of key stakeholders, including community members, policymakers, NGOs, and academic institutions. The proposed SD tools provide practical solutions to overcome barriers, ensuring equitable and effective NbS implementation. This study underscores the importance of integrating structured, stakeholder-centered approaches to address collaboration challenges and enhance the impact of NbS. Future research should focus on applying the proposed framework in practice, gathering empirical evidence to refine and adapt it for diverse contexts.