In this study, a new aero-propulsive model (APM) was derived from the flight manual data of a transport aircraft using Genetic Algorithms (GAs) to perform accurate trajectory predictions. This new GA-based APM provided several improvements to the existing models. The use of GAs enhanced the accuracy of both propulsive and aerodynamic modelling. The effect of compressible drag rise above the critical Mach number, which was not included in previous models, was considered along with the effects of compressibility and profile camber in the aerodynamic model. Consideration of the thrust dependency with respect to Mach number and the altitude in the propulsive model expression was observed to be a more practical approach. The proposed GA model successfully predicted the trajectory for the descent phase, as well, which was not possible in previous models. Close agreement was observed when comparing the time to climb and time to descent values obtained from the model with the flight manual data.