Increasing complexity due to a constantly growing number of target functions turns air traffic trajectory optimization into a multidimensional and nonlinear task that in turn necessitates a focus on the case-sensitive most important criteria. The criteria vary by continent and involve operational, economic, environmental, political, and social concerns. Furthermore, the requirements may alter for a single flight along its journey since air traffic is a transcontinental, segment-wise differently affected transportation mode. Tracked flight data allow for the observation and evaluation of large numbers of flights, as well as the extraction of criteria relevant to flight efficiency and to derive optimization strategies to improve it. In this study, flight track data of China and Europe were compared toward flight efficiency. We found major disparities in both continents’ routing structures. Historical ADS-B data considered to be reference trajectories were assessed for flight efficiency while putting a dedicated focus on the vertical profile. Criteria to optimize vertical flight efficiency (VFE) were derived. Based on the findings, suggestions for improvement towards trajectories with minimum fuel are formulated. Different optimization strategies were tested to identify important input variables and, if possible, to determine differences between operation in China and in Europe. On average and in both regions, the influence of weather (e.g., wind speed and wind direction) exceeds the influence of aerodynamics (aircraft type, mass), as the weather-optimized vertical profile more often results in minimum fuel consumption than the aerodynamically optimized trajectory. Atmospheric conditions, network requirements, aircraft types and flight planning procedures are similar in China and Europe and only have a minor impact on flight efficiency during the cruise phase. In a multi-criteria trajectory optimization of the extracted reference trajectories considering the weather, operational constraints and prohibited areas, we found that in China, on average, just under 13% fuel could be saved through optimal vertical and horizontal routing. In Europe, the figure is a good 10%. Furthermore, we calculated a fuel-saving potential of 8% in China and 3% in Europe through vertical adjustments of the trajectory alone. The resultant reference trajectories will be used for further analysis to increase the efficiency of continental air traffic flows.