The paper presents the sizing of a hybrid electric propulsion system for a prototype aircraft. The main contribution of the paper is to apply multi-objective optimization in the retrofit of a mid-scale aircraft and investigate the fuel economy of the hybrid aircraft for a particular mission cycle. Using the Non-dominated Sorting Genetic Algorithm (NSGA), the fuel consumptions for different flight durations are minimized, which represent the optimal trade-off between fuel consumption and flight duration. With no compromise on endurance and range, the maximum fuel reduction of the retrofitted hybrid aircraft reaches 17.6%, by comparison with the prototype aircraft. The retrofitted aircraft achieves better cruising and climbing performance with the sized hybrid propulsion system. The novelty of the study is the proposal of a new non-dominated sorting algorithm—Benchmark based Non-Dominated Sort (BNDS) for the NSGA. BNDS can reduce the number of comparisons and the time complexity of the non-dominated sorting process. A constraint handling approach is also integrated into the BNDS/NSGA to address performance and mission requirements.