Nature-based solutions (NBSs) can provide answers to the challenges currently facing urban areas related to urban development, densification and climate change. The benefits are well recognized in terms of ecosystem service valuation and include improved air quality, quality of life and human health. They have gained popularity in recent years in addressing environmental issues, especially climate change and air pollution reduction due to potential co-benefits. Some studies suggest that microorganisms associated with the crown of trees (phyllosphere) can enhance their ability to clean air from pollutants. On the one hand, this is due to the metabolites released by microorganisms, which stimulate the development of trees and their resistance to stress, and on the other hand, the microorganisms themselves also participate in the capture and degradation of atmospheric pollutants. The aim of this study is to investigate the potential of some tree species and phyllosphere microbiome to clean air (case study from the city of Plovdiv, Bulgaria). The taxonomic characteristics of the endophytic microflora in the leaves of Fraxinus excelsior, Pinus nigra, Tilia tomentosa and Plantаnus orientalis revealed that they are strongly dependent on environmental conditions and the degree of exposure to the harmful effects of various pollutants. Actinobacteriota and Proteobacteria were the predominant type of microorganisms in all studied leaf samples. A higher abundance of Sphingobacterium, Sphingomonas, Pseudomonas was demonstrated at the genus level and they can serve as potential biomarkers for detecting the impact of various pollutants. It was found that microorganisms in tree leaves, sampled from more polluted areas, had a higher percentage of carbohydrate assimilation and a lower percentage of phenolic compounds assimilation compared to the others. These results could take place in some NBSs with a focus on the converging/degradation/reduction of pollutants by urban trees and the accompanying microorganisms that inhabited different plant organs.