Magellan appartenait à la petite noblesse, mais l'on ne sait presque rien sur son enfance : il fut sans doute page à la cour de Lisbonne. En 1505, il participe à l'expédition vers les Indes orientales de Francisco de Almeida, le futur vice-roi des possessions portugaises. Le premier combat auquel il prend part se produit le 16 mars 1506 devant Cannanore. Magellan est peut-être blessé alors et rapatrié. Il est possible qu'il ait été de nouveau impliqué, dans des affrontements avec les Arabes de l'océan Indien, au début de 1509 : il aurait été encore blessé. Il participe en tout cas à la conquête de la route des épices par les Portugais : il est à Malacca le 11 septembre 1509 et échappe au guet-apens préparé par le sultan de la place. De cette expédition, il ramène un esclave, qui sera son plus fidèle compagnon, Henrique, et une amitié solide, celle de Francisco Serrão, auquel il a sauvé la vie.

   En 1511, Albuquerque étant devenu le vice-roi des Indes portugaises, Magellan s'illustre lors de la prise de Malacca : le chemin des épices, vers les Moluques, est ouvert. Serrão est l'un de ceux qui sont chargés de terminer la tâche. Après un naufrage, il est recueilli par des navigateurs d'Amboine et se fixe à Ternate, où il devient le conseiller du souverain local. Il entre en correspondance avec Magellan : c'est alors que les deux amis imaginent, sans doute, de trouver une route nouvelle vers les Moluques.