Za pieniądze otrzymane od króla, Magellan i Faleiro zakupili 5 statków: „Trinidad” (wyporność 205 ton, załoga 55 osób), statek flagowy Magellana. „San Antonio” (wyporność 120 ton, załoga 60), Juan de Cartagena. „Concepcion” (wyporność 90 ton, załoga 45), Gaspar de Quesada. „Victoria” (wyporność 85 ton, załoga 42), Luis de Mendoza. „Santiago” (wyporność 75 ton, załoga 32), Juan Serrano.
Wyprawa thumb|Magellan w cieśninie swego imienia 10 sierpnia 1519 roku flota pięciu statków pod dowództwem Magellana opuściła Sewillę i popłynęła rzeką Gwadalkiwir do Sanlúcar de Barrameda, gdzie pozostawała przez pięć tygodni. Władze hiszpańskie zachowywały ciągle rezerwę wobec portugalskiego admirała i niewiele brakowało, aby wstrzymały podróż, ale 20 września 1519 roku Magellan wyruszył ostatecznie z 270 członkami załogi.
Usłyszawszy o jego wypłynięciu, portugalski król Manuel I rozkazał jednostkom floty ścigać go, ale Magellan wymknął się Portugalczykom. Po krótkim postoju na Wyspach Kanaryjskich przybył na Wyspy Zielonego Przylądka, skąd wziął kurs na Przylądek Świętego Augustyna w Ameryce Południowej.