Background: The GoGreenRoutes project aims to introduce co-created nature-based solutions (NBS) to enhance environmental quality in six medium-sized cities (Burgas, Lahti, Limerick, Tallinn, Umeå, and Versailles). We estimated the mortality and economic impacts attributed to suboptimal exposure to green space and air pollution, economic impacts, and the distribution thereof the adult population by socioeconomic status. Methods: We retrieved data from publicly accessible databases on green space (NDVI and % Green Area), air pollution (NO2 and PM2.5) and population (≥20 years, n = 804,975) at a 250m × 250m grid-cell level, and mortality for each city for 2015. We compared baseline exposures at the grid-cell to World Health Organization’s recommendations and guidelines. We applied a comparative risk assessment to estimate the mortality burden attributable to not achieving the recommendations and guidelines. We estimated attributable mortality distributions and the association with income levels. Results: We found high variability in air pollution and green spaces levels. Around 60% of the population lacked green space and 90% were exposed to harmful air pollution. Overall, we estimated age-standardized mortality rates varying from 10 (Umeå) to 92 (Burgas) deaths per 100,000 persons attributable to low NDVI levels; 3 (Lahti) to 38 (Burgas) per 100,000 persons to lack of % Green Area; 1 (Umeå) to 88 (Tallinn) per 100,000 persons to exceedances of NO2 guidelines; and 1 (Umeå) to 206 (Burgas) per 100,000 persons to exceedances of PM2.5 guidelines. Lower income associated with higher or lower mortality impacts depending on whether deprived populations lived in the densely constructed, highly-trafficked city centre or greener, less polluted outskirts. Conclusions: We attributed a considerable mortality burden to lack of green spaces and higher air pollution, which was unevenly distributed across different social groups. NBS and health-promoting initiatives should consider socioeconomic aspects to regenerate urban areas while providing equally good environments.