For long flights, the cruise is the longest phase and where the largest amount of fuel is consumed. An in-cruise optimization method has been implemented to calculate the optimal trajectory that reduces the flight cost. A three-dimensional grid has been created, coupling lateral navigation and vertical navigation profiles. With a dynamic analysis of the wind, the aircraft can perform a horizontal deviation or change altitudes via step climbs to reduce fuel consumption. As the number of waypoints and possible step climbs is increased, the number of flight trajectories increases exponentially; thus, a genetic algorithm has been implemented to reduce the total number of calculated trajectories compared to an exhaustive search. The aircraft’s model has been obtained from a performance database, which is currently used in the commercial flight management system studied in this paper. A 5% average flight cost reduction has been obtained.