In this paper we investigate the optimal taxation of CO2 and its co-pollutants. While CO2 is a uniformly mixed stock pollutant, important CO2 co-pollutants like SO2, PM2.5 and PM10 are flow pollutants with spatially differentiated damages. Recent proposals have called for CO2 control that accounts for its effects on emissions of its co-pollutants, which implies that optimal CO2 taxes would have a spatial component. However we demonstrate that setting a CO2 tax that varies from its marginal damage is justified only if co-pollutants are regulated inefficiently. We demonstrate that the optimal CO2 tax deviates from the CO2 marginal damage across sources depending on the source-specific co-pollutant marginal damage, the level of inefficiency in the co-pollutant regulation, and the abatement cost interaction of the two pollutants. An alternative to adjusting CO2 policy to account for the inefficient regulation of a co-pollutant is to address the inefficiency directly by modifying the regulation of the co-pollutant. Since this approach is more efficient in general, we quantify the expected reduction in social costs from this regulation relative to adjusting CO2 taxes. With a simulation of CO2 and SO2 control from the U.S. power sector, we find that setting efficient taxes for both CO2 and SO2 provides a welfare gain that is likely to be many orders of magnitude greater than the gain from adjusting CO2 taxes to account for the inefficient regulation of SO2.