Nature-based solutions have emerged as a concept for integrating ecosystem-based approaches whilst addressing multiple sustainable development goals. However, implementing nature-based solutions is inherently complex and requires consideration of a range of environmental and socio-economic conditions that may impact on their effectiveness. This research assesses ecosystem services within the Valletta urban agglomeration, Malta, and evaluates the implications arising from existing distributional patterns. Proxy-based indicators and expert knowledge were used to map and assess a set of 14 ecosystem services. Proximity and correlation analyses were used to assess distributional inequalities arising from differentiated availability of ecosystem types with high ecosystem service capacities for groups with different socio-economic characteristics. Data relating to schooling, employment, sickness, disability, and old age, were combined to identify areas of relative advantage and disadvantage. The highest ecosystem service capacities were in the urban fringes and the lowest in dense urban cores. Private gardens and urban trees had the highest regulating ecosystem service capacities per unit area. Contrastingly, public gardens had low effectiveness for regulating ecosystem services but the highest cultural ecosystem service capacities. Availability of urban green infrastructure and tree cover differ according to socio-economic advantage, and disadvantaged communities generally had reduced proximity to ecosystems with high ecosystem service capacities. Considering these findings, we argue that urban ecosystem service assessments can support greening strategies by identifying the most effective nature-based solutions that can play a redistributive role by addressing existing inequalities in green infrastructure and ecosystem services capacities distribution in cities.