Nature-based solutions and green urban infrastructures are becoming common measures in local air quality and climate strategies. However, there is a lack of analytical frameworks to anticipate the effect of such interventions on urban meteorology and air quality at a city scale. We present a modelling methodology that relies on the weather research and forecasting model (WRF) with the building effect parameterization (BEP) and the community multiscale air quality (CMAQ) model and apply it to assess envisaged plans involving vegetation in the Madrid (Spain) region. The study, developed within the VEGGAP Life project, includes the development of two detailed vegetation scenarios making use of Madrid’s municipality tree inventory (current situation) and future vegetation-related interventions. An annual simulation was performed for both scenarios (considering constant anthropogenic emissions) to identify (i) variations in surface temperature and the reasons for such changes, and (ii) implications on air-quality standards according to EU legislation for the main pollutants (PM10, PM2.5, NO2 and O3). Our results suggest that vegetation may have significant effects on urban meteorology due to changes induced in relevant surface properties such as albedo, roughness length or emissivity. We found a net-heating effect of around +0.18 °C when trees are introduced in dry, scarcely vegetated surfaces in the city outskirts. In turn, this enhances the planetary boundary layer height (PBLH), which brings about reductions in ambient concentrations of relevant pollutants such as NO2 (in the range of 0.5–0.8 µg m−3 for the annual mean, and 2–4 µg m−3 for the 19th highest 1 h value). Conversely, planting new trees in consolidated urban areas causes a cooling effect (up to −0.15 °C as an annual mean) that may slightly increase concentration levels due to less-effective vertical mixing and wind-speed reduction caused by increased roughness. This highlights the need to combine nature-based solutions with emission-reduction measures in Madrid.