Air traffic alters the atmospheric composition and thereby contributes to climate change. Here we investigate the trans-Atlantic air traffic for one specific winter day and analyse, which routing changes were required to achieve a reduction in the air traffic’s contribution to climate change. We have applied an atmosphere-chemistry model to calculate so-called five dimensional climate cost functions (CCF), which describe the climate effect of a locally confined emission. The five dimensions result from the emission location (3D), time (1D) and the type of emission (1D; carbon dioxide, water vapour, nitrogen oxides). In other words, carbon dioxide (CO2), water vapour (H2O) and nitrogen oxides (NOx) are emitted in amounts typical for aviation at many confined locations and times and their impacts on climate calculated with the atmosphere-chemistry model. The impact on climate results from direct effects, such as the changes in the concentration of the greenhouse gases CO2 and H2O and indirect effects such as contrail cirrus formation and chemical changes of ozone and methane by emissions of NOx. These climate cost functions are used by a flight planning tool to optimise flight routes with respect to their climate impact and economic costs of these routes. The results for this specific winter day show that large reductions in the air traffic’s contribution to climate warming (up to 60%) can be achieved for westbound flights and smaller reductions for eastbound flights (around 25%). Eastbound flights take advantage of the tail winds from the jet stream and hence routings with lower climate impacts have a large fuel penalty, whenever they leave the jet stream. Maximum reduction in climate impact increases the economic costs by 10 to 15%, due to higher fuel consumption, caused by a longer flight distance and lower flight levels. However, with only small changes to the air traffic routings and flight altitudes, climate reductions up to 25% can be achieved by only small changes in economic costs (less than 0.5%).