In recent years nature-based solutions (NBS) have received increasing attention as a way to enhance urban resilience. NBS are often presented as an alternative or combination to grey infrastructure in disaster risk reduction and climate adaptation. More generally, they are seen as a deliberate intervention that seeks to use the properties of nature to simultaneously provide environmental, social, and economic benefits to address multifaceted challenges that cities face. Despite the recognized potential and benefits that NBS can offer, related knowledge is so far scarce and fragmented and the use of NBS for increasing urban resilience remains limited. To better understand the potential of NBS and their local implementation, we identify successful governance, finance, and public participation practices and the associated conditions that can enable (or limit) the emergence of NBS in cities. Based on an in-depth case study approach and in close collaboration with practitioners, we study how NBS have so far been implemented in some selected cities: Malmö, Melbourne, and Munich. Our results show how NBS governance emerges as a complex phenomenon, involving multiple social and political actors as well as diverse institutional and financial challenges, such as uneven landscapes of socio-economic power relations and inequalities in access to financing. Participative and reflexive forms of governance are central to overcome these challenges to support long-term social learning, new means of decision-making and new forms of citizen involvement.