With their potential to effectively address multiple urban sustainability challenges, the emerging policy discourse on nature-based solutions seeks to encourage the development of multifunctional nature for sustainable and just cities. Nature-based solutions, however, are vulnerable to co-option by powerful interests in ways that limit their contribution to a broad range of sustainability goals. Reflexive governance arrangements between different types of actors, engaging in continuous and iterative processes of learning and readjustment of institutions and practices, provide a way to address this issue. However, the potential of reflexive governance in increasing commitment to sustainable and just cities, and the role of power struggles in such processes, remains underexplored. To study this question, we undertake a comparative case study analysis of nature-based solutions in Utrecht (The Netherlands), Malmö (Sweden), and Utsunomiya (Japan). These are analyzed using a framework structured around the dimensions of system analysis, goal formulation, and strategy implementation, to which we apply a justice lens. The findings demonstrate reflexive processes in each of the studied cases, but the justice dimension is not always explicitly taken into account or clearly influenced in positive ways. We unveil tensions between the ideal of sustainable and just cities and the reality of urban nature-based solution initiatives being partially dependent on the power structures they seek to influence for their continued existence. We argue against dismissing the studied cases as neoliberal projects on these grounds. Reflexive governance for sustainable and just cities entails a continuous struggle for dominance between different ideas and interests. Moreover, the battlegrounds for these struggles may look very different across sociopolitical contexts. Provided that justice considerations are continually present, reflexive governance of urban nature-based solutions is likely to contribute to more sustainable and just cities.