En 1512, Magellan est de retour à Lisbonne, où il peut mûrir son projet. Le service de la Couronne le conduit l'année suivante au Maroc, où il est blessé au genou dans une expédition contre les Maures : il claudiquera jusqu'à la fin de ses jours. Accusé de malversation, il prend sur lui de revenir se défendre devant son roi, sans passer par la voie hiérarchique : il est mal reçu par Manuel I^er, qui l'éconduira de nouveau lorsqu'il demandera une modeste réévaluation de sa pension.

   Il se lie alors avec un cosmographe, Ruy Faleiro, avec lequel il développe son projet de voyage vers les Moluques. C'est sans doute de bonne foi, et non poussés par quelque ressentiment vis-à-vis de leur souverain, que les deux hommes en viennent à considérer que les Moluques dépendent plutôt de la couronne d'Espagne que de celle du Portugal : les bulles de 1493 et le traité de Tordesillas ne pouvaient être précis quant à la ligne partageant ces confins de l'Asie, que l'on imaginait proches de l'Amérique espagnole. Dès lors, ce n'est pas une trahison que de se tourner vers Charles I^er, le futur Charles Quint, pour mettre sur pied le nouvel itinéraire, qui utiliserait pour la première fois la rotondité de la Terre.

   Magellan arrive à Séville en 1517 et se place sous la protection d'un Portugais passé au service de l'Espagne et devenu commandeur de l'ordre de Santiago, Duarte Barbosa (vers 1480-1521). Il peut ainsi entrer en rapport avec de hauts personnages, et en particulier avec Juan de Aranda, haut fonctionnaire très influent à la « Casa de Contratación », organisme qui traite les affaires des Indes. Finalement, Charles I^er lui accorde pour dix années l'exclusivité de la recherche qu'il préconise (22 mars 1518). La Couronne prend les frais à sa charge ; Magellan et Faleiro recevront le vingtième des revenus des terres découvertes.

   Le voyage va être préparé activement, malgré les intrigues des Portugais, qui voudraient bien, maintenant, tenter de le faire remettre. Cinq navires sont confiés à Magellan, avec 265 hommes. Au dernier moment, on embarque l'Italien Antonio Pigafetta (1480 ou 1491-vers 1534), qui sera l'historiographe de l'entreprise et l'un des rares survivants. Le représentant du roi d'Espagne est Juan de Cartagena, commandant le San Antonio et avec lequel Magellan entretiendra très vite des rapports difficiles.