Current air traffic routing is motivated by minimizing economic costs, such as fuel use. In addition to the climate impact of CO2 emissions from this fuel use, aviation contributes to climate change through non-CO2 impacts, such as changes in atmospheric ozone and methane concentrations and formation of contrail-cirrus. These non-CO2 impacts depend significantly on where and when the aviation emissions occur. The climate impact of aviation could be reduced if flights were routed to avoid regions where emissions have the largest impact. Here, we present the first results where a climate-optimized routing strategy is simulated for all trans-Atlantic flights on 5 winter and 3 summer days, which are typical of representative winter and summer North Atlantic weather patterns. The optimization separately considers eastbound and westbound flights, and accounts for the effects of wind on the flight routes, and takes safety aspects into account. For all days considered, we find multiple feasible combinations of flight routes which have a smaller overall climate impact than the scenario which minimizes economic cost. We find that even small changes in routing, which increase the operating costs (mainly fuel) by only 1% lead to considerable reductions in climate impact of 10%. This cost increase could be compensated by market-based measures, if costs for non-CO2 climate impacts were included. Our methodology is a starting point for climate-optimized flight planning, which could also be applied globally. Although there are challenges to implementing such a system, we present a road map with the steps to overcome these.