Green Infrastructure (GI) practices have shown to be promising in mitigating the air pollution in urban areas of several cities across the world. GI practices such as trees, green roofs and green walls are widely used in United States and Europe to mitigate the air pollution. However, there is yet limited knowledge available in identifying the most suitable GI strategy for an urban area in improving the air quality. Furthermore, it is evident that Australia is still lagging behind in adapting GI to mitigate air pollution, compared with US and Europe. Therefore, this study analyzed the air quality improvement through several GI scenarios consisting of trees, green roofs and green walls considering a case study area in Melbourne, Australia by using the i-Tree Eco software. The results were compared with case studies in different cities across the world. The results showed that the i-Tree Eco software can be successfully applied to an Australian case study area to quantify the air quality improvement benefits of GI. The results were further assessed with several environmental, economic and social indicators to identify the most suitable GI scenarios for the study area. These indicators were quantified using different methods, to assess the effectiveness of different GI scenarios. The results showed that, trees provided the highest air pollution removal capability among the different GI considered for the study area. Combination of different GI such as green roofs and green walls with trees did not provide a significant increment of air quality improvement however, has provided more local benefits such as building energy savings. The results obtained from this study were also beneficial in developing policies related to future GI applications in major cities of Australia for the air quality improvement.