As cities increasingly turn to nature-based solutions to address key urban socio-ecological challenges, approaches to their governance, planning and implementation are increasingly important for ensuring their effectiveness. Nature-based solutions are multifunctional, and so their planning and implementation are by necessity interdisciplinary. As such, to support urban transitions with nature-based solutions, the role of intermediary actors deserves research attention. Intermediaries play key roles in linking between sectors, across different levels of government and between disciplines and policy domains. We identified three key points for research and planning nature-based solutions through intermediaries as key agents for change: intermediaries are creators of enabling institutional spaces needed for mainstreaming nature-based solutions in cities; intermediaries as actor configurations are dynamic over time and in context, and intermediation has to be understood as a fundamental governance activity in cities that want to scale up their climate adaptation planning with nature-based solutions. Using a case study of the development and initial implementation of the metropolitan urban forest strategy in Melbourne Australia, we analyze the multi-actor landscape that emerged, through the lens of intermediation. We systematically investigated which actors, partnerships and platforms acted as intermediaries in the transformative agenda of the Urban Forest strategy, how these actors interacted over the course of the strategy’s development and how their roles and functions shifted during the early implementation stages of the strategy. We found that an ‘ecology of intermediaries’ adopted a range of roles to support key functions including building collaboration, informing and disseminating policy learning, and strengthening political support. While intermediaries’ roles and functions shifted across the strategy’s development, their contributions were critical in the complex metropolitan governance context. Collaborative planning and governance for nature-based solutions in cities require intermediaries to remain topical, focused and inclusive/open to new ideas and lessons from innovations both emerging and driven.