Военным кораблям успешно удалась операция, и в 1511 году Магеллан принимает участие в походе 19 кораблей королевства на Малакку. Город был захвачен, и Магеллан отправляется домой. В июле 1512 года он уже в Лиссабоне, где ему назначается пенсия, причем самая маленькая из возможных, всего в 1000 реалов, которых не хватало на достойную жизнь.
Магеллану пришлось снова надеть военную форму. В 1514 году в одном из боев под марокканским городом Аземмур он был ранен в ногу, после чего хромал всю оставшуюся жизнь, в другом под ним застрелили лошадь. Хромающему, да еще и потерявшему лошадь офицеру поручили охранять отбитый у мавров скот, но вскоре обвинили в том, что он тайно продал бывшим хозяевам часть стада.
Оскорбленный Магеллан покинул без разрешения расположение части и отправился в Лиссабон, но аудиенции у короля добиться не смог. Мало того, монарха возмутило поведение Магеллана, и тот был вынужден вернуться в Марокко. К тому времени вора поймали, все обвинения с Фернана сняли, но он подал в отставку и вернулся домой.
По-видимому, именно тогда у Магеллана возникла мысль о путешествии, которое его прославит. Америка была уже открыта, но почти не исследована. Фернан изучает карты, беседует с опытными мореплавателями и астрономами. Вскоре он окончательно уверился, что существует проход через материк, который сократит расстояние до Индии и «островов пряностей» во много раз, и начал действовать. Король Португалии Мануэль I, у которого Фернан просит дать ему возможность вернуться во флот и отправиться в путешествие, отвечает отказом, но не возражает, если такую возможность предоставят Магеллану другие владыки. Будущему великому мореплавателю пришлось перебраться в Севилью.
Хуана де Аранда, из Севильской палаты контрактов, занимающейся организацией экспедиций, за 1/8 от возможной прибыли от путешествия организовал встречу Магеллана с королем Испании. Впоследствии де Аранду оттеснили от участия в разделе прибылей, и 22 марта 1518 года был заключен новый договор между Магелланом и его компаньоном астрономом Фалеру — с одной стороны, и королем Испании Карлом I — с другой, согласно которому оба мореплавателя могли получить 1/5 часть чистых доходов от плавания, права наместничества на открытых территориях, 1/20 часть от прибылей, получаемых на новых землях, и право на два острова, если таковых будет открыто не менее 6. Получив добро, Фернан приступает к подготовке экспедиции.
20 сентября 1519 года эскадра в пять кораблей с 265 членами экипажей на бортах, возглавляемая флагманом «Тринидадом» с Магелланом на капитанском мостике, покинула испанский порт, расположенный на берегу Атлантического океана, и направилась в сторону Нового Света. При пересечении океана за счет использования разработанной Магелланом системы оповещения корабли флотилии ни одного раза не потеряли друг друга из вида.
Два месяца потребовалось флотилии, чтобы достичь берегов Бразилии, и еще один — широкого водоема, который окажется рекой Ла Платой. Невысокая скорость передвижения у берегов Южной Америки вызвана тщательностью обследования любого залива, глубоко вдающегося в сушу. Немало времени ушло и на обследование Ла Платы, прежде чем Магеллан не убедился, что это не пролив, а устье гигантской реки. Эскадра медленно двигалась к югу, тщательно исследуя берег. Во время одной из стоянок моряки первые из европейцев увидели пингвинов. Мореплаватели решили, что это аборигены, и продолжали в это верить до тех пор, пока во время зимовки не встретились с людьми, населяющими Огненную Землю. Позднее открытый в экспедиции вид пингвинов получил название «магеллановый».
Приближалась зима, и 31 марта 1520 года флотилии пришлось встать на зимовку в бухте, получившей название в честь Святого Юлиана. Ныне это провинция Санта-Круз в Аргентине.
К маю море немного успокоилось, и путешественники решились на активные действия. Магеллан послал в южном направлении небольшой корабль «Сантьяго», но тот потерпел кораблекрушение и погиб. Команде, за исключением одного человека, удалось спастись и направиться по берегу в сторону остальной эскадры. Несколько недель прошло, прежде чем им удалось объединиться. Потеря была очень тяжелой, и дело даже не только в гибели судна, специально построенного для проведения разведки, пропала значительная часть продовольствия, которое находилось в трюме «Сантьяго». Пришлось продолжить зимовку, соблюдая режим строжайшей экономии.
Пока корабли стояли в бухте, к ним приблизились аборигены. Это были люди очень высокого роста, которые для утепления обматывали ноги сеном. Мореплаватели прозвали их патагонцами, то есть людьми большеногими, или рожденными с лапами. Страна по аналогии получила название Патагония. Исполняя волю короля — доставить в Испанию представителей всех встреченных на пути народов, путешественникам удалось захватить двух индейцев, но ни одному не удалось дожить до возвращения в Европу.
Наконец зима закончилась, и корабли тронулись в путь. 21 октября 1520 года, то есть через год после начала плавания, перед путешественниками показался узкий пролив, уходящий вглубь материка. С южной стороны ночами моряки часто наблюдали отблески огня. Решив, что это последствия вулканической деятельности, Магеллан назвал эту землю Огненной. Посланные на разведку два корабля вскоре вернулись с вестью о возможности сквозного прохода через континент. Магеллан решил рискнуть, и флотилия отправляется в путь.
Через 38 дней перед мореплавателями расстилался спокойный безбрежный океан. 28 ноября 1520 года навсегда вошло в мировую историю как дата окончания первого прохода корабля из Атлантического океана в Тихий.
Пролив был назван Магелланом в честь праздника Всех Святых, но был впоследствии переименован королем Испании и с тех пор по праву носит имя своего первопроходца — Магеллана. Океан, который встретил мореплавателей, выбравшихся из круговерти пролива, полным штилем с прекрасной погодой, был назван Магелланом Тихим.