The Kyoto Protocol assigns limits for the aggregate emissions of six greenhouse gases, but most economic analyses focus on CO2 abatement. What are the potential gains if policy makers exploit the flexibility in a multi-gas abatement strategy? We extend the EDGE model to include sinks and non-CO2 gases and show that a multi-gas strategy reduces costs by 20-35% in the Western Annex B countries. Marginal abatement costs decrease around 30%, and the cost-effective abatement mix involves relatively more abatement of the non-CO2 gases, which offers many low costs abatement options. Lower marginal abatement costs decrease domestic action by reducing the costs of emissions imports, whereas more low cost abatement options increases domestic action. The low cost abatement options increase domestic action, whereas lower marginal abatement costs reduces domestic action by making imports of emissions cheaper. The net effect of a multi-gas strategy on domestic action is therefore not given a priori. We show that a multi-gas strategy reduces domestic action around 2% in the United States and increases domestic action by around 8% in the European Union. Our sensitivity analyses finally show that the relatively weak growth in non-CO2 baseline emissions accounts for a large share of the savings associated with a multi-gas strategy.