Africa is urbanizing at an astonishing rate. To meet many of the Sustainable Development Goals there will be a requirement for cities in sub-Saharan Africa to plan for, and manage, the rapid rise in the urban population. Green infrastructure has the potential to provide multiple ecosystem services to benefit the urban population. The general objective of this review is to consolidate research undertaken on urban green infrastructure and the associated ecosystem services in sub-Saharan African cities. The 68 reviewed papers spanned 20 countries and included 74 urban areas. However, only 38% of sub-Saharan countries had any research carried out in them. The most represented ecosystem services were regulating and provisioning, with supporting services getting the least attention. Overall there was a lack of in-depth studies on all ecosystem services, especially supporting and cultural services. Seven overarching categories of barriers and challenges to the sustainable delivery of ecosystem services emerged from the reviewed papers, namely: (i) socio-cultural values, traditions and perceptions; (ii) lack of capacity; (iii) governance, urban planning and social inequality; (iv) lack of data and/or case studies; (v) ecosystem disservices; (vi) spatial trade-offs and conflicts; (vii) climate change. These barriers we identified will need to be addressed if the future, long-term sustainable provision of ecosystem services in sub-Saharan African cities is to be assured.