In this paper we apply a novel black-box optimisation algorithm to the Global Trajectory optimisation Problem provided by the European Space Agency (ESA). The proposed algorithm, called SAGES, has been applied to instances of seven trajectory design problems, comparing it with the known best solutions. The numerical results show clear improvements on the majority of the problems and, in order to investigate deeply the problems, a sensitivity and solutions robustness analysis has been performed, measuring the influence of each single variable to the objective function. © Springer-Verlag London Limited 2011.