Aircraft do not fly through a vacuum, but through an atmosphere whose meteorological characteristics are changing because of global warming. The impacts of aviation on climate change have long been recognised, but the impacts of climate change on aviation have only recently begun to emerge. These impacts include intensified turbulence and increased take-off weight restrictions. Here we investigate the influence of climate change on flight routes and journey times. We feed synthetic atmospheric wind fields generated from climate model simulations into a routing algorithm of the type used operationally by flight planners. We focus on transatlantic flights between London and New York, and how they change when the atmospheric concentration of carbon dioxide is doubled. We find that a strengthening of the prevailing jet-stream winds causes eastbound flights to significantly shorten and westbound flights to significantly lengthen in all seasons. Eastbound and westbound crossings in winter become approximately twice as likely to take under 5 h 20 min and over 7 h 00 min, respectively. For reasons that are explained using a conceptual model, the eastbound shortening and westbound lengthening do not cancel out, causing round-trip journey times to increase. Even assuming no future growth in aviation, the extrapolation of our results to all transatlantic traffic suggests that aircraft will collectively be airborne for an extra 2000 h each year, burning an extra 7.2 million gallons of jet fuel at a cost of US$ 22 million, and emitting an extra 70 million kg of carbon dioxide, which is equivalent to the annual emissions of 7100 average British homes. Our results provide further evidence of the two-way interaction between aviation and climate change.