Nature-based solutions (NBS) are championed for providing co-benefits to cities and residents, yet their environmental justice impacts are increasingly debated. In this paper, we explore whether and how hybrid governance approaches, such as Mosaic Governance, may contribute to just transformations and sustainable cities through fostering long-term collaborations between local governments, local communities, and grassroots initiatives. Based on case studies in three major European cities, we propose and then exemplify six possible pathways to increase environmental justice: greening the neighborhood, diversifying values and practices, empowering people, bridging across communities, linking to institutions, and scaling of inclusive discourses and practices. Despite the diversity of environmental justice outcomes across cases, our results consistently show that Mosaic Governance particularly contributes to recognition justice through diversifying NBS practices in alignment with community values and aspirations. The results demonstrate the importance of a wider framing of justice in the development of NBS, sensitive to social, cultural, economic and political inequities as well understanding potential pathways to enhance not only environmental justice, but also social justice at large. Especially in marginalised communities, Mosaic Governance holds much potential to advance social justice by enabling empowering, bridging, and linking pathways across diverse communities and NBS practices.