Since most Green House Gases (GHGs) and air pollutants are generated from the same sources, it will be cost-effective to develop a GHGs reduction plan in combination with simultaneous removal of air pollutants. However, effects on air pollutants reduction according to implementing any GHG abatement plans have been rarely studied. Reflecting simultaneous removal of air pollutants along with the GHGs emission reduction, this study investigated relative cost effectiveness among GHGs reduction action plans in Busan Metropolitan City. We employed the Data Envelopment Analysis (DEA), a methodology that evaluates relative efficiency of decision-making units (DMUs) producing multiple outputs with multiple inputs, for the investigation. Assigning each GHGs reduction action plan to a DMU, implementation cost of each GHGs reduction action plan to an input, and reduction potential of GHGs and air pollutants by each GHGs reduction action plan to an output, we calculated efficiency scores for each GHGs reduction action plan. When the simultaneous removal of air pollutants with the GHGs reduction were considered, green house supply-insulation improvement and intelligent transportation system (ITS) projects had high efficiency scores for cost-positive action plans. For cost-negative action plans, green start network formation and running, and daily car use control program had high efficiency scores. When only the GHGs reduction was considered, project priority orders based on efficiency scores were somewhat different from those when both the removal of air pollutants and GHGs reduction were considered at the same time. The expected action plan priority difference is attributed to great difference of air pollutants reduction potential according to types of energy sources to be reduced.