This paper presents the results of a research performed at the Research Laboratory in Active Controls, Avionics and Aeroservoelasticty (LARCASE), at ÉTS, concerning optimisation strategies for cruise flight segments with imposed flight time (delimited by waypoints with required time of arrival constraints). Specifically, a new algorithm is presented that identifies the optimal vertical navigation profile (flight altitude and speed optimisation) for a cruise segment with imposed lateral navigation profile, bounded by two waypoints with required time of arrival constraints. The set of evaluated vertical navigation profiles are characterised by identical altitudes and speeds at their initial and final waypoints (at the beginning and the end of the cruise segment under optimisation), a maximum of one altitude step (relative to the initial altitude), and are flown at constant speed. This study investigates the flight performance increase (total cost reduction) for a flight along the optimal vertical navigation profile, relative to a flight at the optimal speed and initial cruise altitude. The evaluation was performed using a medium haul transport aircraft flight performance model, for three lateral navigation profiles and three wind profiles. The algorithm is targeted for Flight Management Systems platforms, to provide the optimal flight trajectory for the imposed lateral flight profile and time constraints.