Climate change is an urgent challenge in urban planning. Weather extremes and resulting impacts such as heat waves and flash floods are already influencing the quality of life in cities and impact on infrastructure, human health and city life. In this study, we investigated perception of and economic preferences for adaptation to climate change in one of Europe’s capital cities to inform its planning policy. Through a choice experiment, we elicit the preferences of a sample (n = 550) from Prague, Czech Republic, for a citywide policy which would increase the use of six commonly used nature-based solutions (NBS) in public spaces and on public buildings across the city. Three attributes were used to describe this policy: (i) the locations where NBS would predominantly be implemented, (ii) the species diversity of these measures, and (iii) their implied costs for households. Our results showed that the NBS policy is widely supported by the public over the status quo and that this preference is mirrored in citizens’ concerns about climate change and the risks posed by heatwaves particularly. Species diversity matters in the portrayed scenarios, suggesting that (bio)diverse NBS generate additional public value over single species measures and that policy which targets biodiversity may gain support. Implementation of NBS in public spaces (e.g., street trees, rain gardens) is preferred over measures implemented on public buildings (green roofs and facades). Furthermore, adverse experiences with heatwaves has increased support for the policy. The presented results provide evidence that adaptation planning through NBS is likely to generate significant public value which is expected to increase with the intensifying effects of climate change.