Impacts of climate change are often acute for those who live in informal settlements, the places where poverty, inequality and deprivation are concentrated in cities across the developing world. To broaden the strategies to address this issue, many cities are now embracing ecosystem-based adaptation and resilience. But, in Sub-Saharan Africa (SSA) the approach is yet to make much headway. This paper examines how climate change impacts on poor urban people via one component of urban ecosystem - urban green structures (UGS) - in Dar es Salaam, Tanzania. It examines: the UGS of importance to the city's informal dwellers and the range of derived services; changes over time to these UGS and derived services; and emerging adaptation practices. Using qualitative methods, the study has three key findings. First, cultural ecosystem services are of greatest importance to informal dwellers, although they do harness a range of other services. Second, the city's UGS have undergone dramatic changes due to both climatic and non-climatic factors. This has resulted in a gradual decline in the quantity and quality of UGS-derived services for the urban poor. Third, in responding to these changes, informal settlement dwellers have relied mostly on their personal, and sometimes on their collective, resources and capabilities. There are some innovative practices that draw on external institutions, but access to external support for informal communities has remained consistently low. City authorities should approach and plan greening 'for' (not 'in') informal settlements as a targeted environmental improvement endeavour - referred to here as 'creative urban planning'.