Nature-based solutions in their most basic and accessible form as public green spaces and urban trees are often in dire condition, exacerbated by the effects of climate change. Lack of maintenance further reduces the ability to provide ecosystem services and hinders long-term sustainability. Examples from four cities in Australia, Asia, Europe, and Latin America are used to discuss the importance of strategic planning for implementing nature-based solutions as well as proper maintenance. We suggest (1) specific legal and political frameworks, (2) foresight in planning stages, (3) optimized provision of benefits by considering scale, design, and distribution, (4) prioritization of nature-based solutions with both high social and ecological benefits, (5) careful retrofitting of existing green spaces, (6) balanced ratio of resource input and benefits, (7) sustained commitment for long-term care, and (8) enhanced public participation.