In this paper the preliminary design of multiple gravity-assist trajectories is formulated as a global optimization problem. An analysis of the structure of the solution space reveals a strong multimodality, which is strictly dependent on the complexity of the model. On the other hand it is shown how an oversimplification could prevent finding potentially interesting solutions. A trajectory model, which represents a compromise between model completeness and optimization problem complexity is then presented. The exploration of the resulting solution space is performed through a novel global search approach, which hybridizes an evolutionary based algorithm with a systematic branching strategy. This approach allows an efficient exploration of complex solution domains by automatically balancing local convergence and global search. A number of difficult multiple gravity-assist trajectory design cases demonstrates the effectiveness of the proposed methodology.