China's high-speed economic development and reliance on overconsumption of natural resources have led to serious environmental pollution. Environmental taxation is seen as an effective economic tool to help mitigate air pollution. In order to assess the effects of different scenarios of environmental taxation policies, we propose a frontier-based environmentally extended input-output optimization model with explicit emission abatement sectors to reflect the inputs and benefits of abatement. Frontier analysis ensures policy scenarios are assessed under the same technical efficiency benchmark, while input-output analysis depicts the wide range of economic transactions among sectors of an economy. Four scenarios are considered in this study, which are increasing specific tax rates of SO2, NOx, and soot and dust separately and increasing all three tax rates simultaneously. Our estimation results show that: raising tax rates of SO2, NOx, and soot and dust simultaneously would have the highest emission reduction effects, with the SO2 tax rate making the greatest contribution to emission reduction. Raising the soot and dust tax rate is the most environmentally friendly strategy due to its highest abatement to welfare through avoided health costs. The combination of frontier analysis and input-output analysis provides policy makers a comprehensive and sectoral approach to assess costs and benefits of environmental taxation.