Today’s airline industry is facing a highly competitive market, so network and trajectory optimization is driven by fuel and time costs, constrained by air traffic management capacity. The resulting climate effects on global warming and on environmental health are reflected in the emission trading system (ETS) certificates. However, the climate impact of air traffic depends on the locality of the emissions. Hence, even the airline network structure affects the air traffic climate impact. This paper presents an approach of the back coupling of network and trajectory optimization, aiming to minimize both climate effects and costs. First, an optimized air traffic network with respect to minimum fuel consumption and minimum climate costs due to latitude-dependent effects of nitric oxides is compared with a fuel burn optimized network. Second, a lateral trajectory optimization gives the horizontally shortest flight path with respect to minimum costs due to the latitude-dependent effects of nitric oxides. In a third step, vertical trajectory optimization is applied within the optimized routing structure. The calculated amount of emissions is transferred into carbon dioxide equivalent emissions using the global warming potential. Finally, the emissions are expressed in costs considering the effect of the emissions on global warming with the help of the ETS. These costs are used to evaluate both networks, with and without nitric oxide consideration.