Addressing air pollution is one of the main public policies in Seoul. The national authority and the city of Seoul have spent a huge amount of money for air pollution management to increase the quality of life and well-being of the general public. It is well known that the benefit of air pollution management is far higher than the cost. Moreover, mitigation of air pollution can contribute to reducing inequalities and promoting sustainable development. This research investigates the cost-effectiveness of air pollution policy measures in Seoul. We set up a database on air pollution measures in Seoul and calculated the cost and emission reduction of each measure. In addition, by applying random forest models, the effect of policy measures on nitrogen oxides (NOx) concentration was investigated. We classified the policy measures into 10 groups and assessed the cost-effectiveness. One of the main findings was that the demand control of transportation is most cost effective in emission reduction of air pollutants in Seoul, followed by management of vehicles in use and management of non-road mobile sources, such as construction vehicles. We also performed a multi-criteria analysis on the same policy measures and found that the policy priorities recommended from the two methods are generally consistent.