Подготовка к плаванию началась довольно рано вслед за королевским указом, но продолжалась она необычно долго из-за беспардонного мошенничества поставщиков, скрытого сопротивления Дома Торговли, саботажа Португалии и неожиданных помех со стороны, как вскоре выяснилось, серьезно терявшего рассудок Фалейру, которого в итоге пришлось заменить на капитана Хуана де Картахена. Почти неизбежные в таких случаях обманы подрядчиков-снабженцев на сей раз оказались особенно частыми и крупными. Они ухитрились даже поставить старые залатанные каравеллы, не говоря уже о плохого качества продуктах и прочих запасах. Могущественный епископ Фонсека — самый влиятельный человек в Доме торговли и член королевского совета — все время задерживал утверждение достойных кандидатур на руководящие посты экспедиции, стремясь навязать Магеллану вместо них своих многочисленных некомпетентных родственников и фаворитов, которые по его замыслу должны были в ходе плавания взять руководство экспедицией в свои руки и избавиться от ненавистного португальца. Узнав о решении Карла Пятого утвердить план Магеллана, Лиссабон, осознав, видимо, свой просчет, теперь через своего посла в Испании приступил к самому настоящему саботажу его осуществления. Среди прочих таких попыток Магеллану было предложено большое вознаграждение, если он откажется от этой экспедиции и вернется в Португалию. Более того, один из советников и духовников Дона Мануэля епископ Васконсельос даже предложил убить Магеллана. Безрассудное поведение главного партнера мореплавателя создавало тоже немало ненужных препятствий и задерживало время начала путешествия. Но все эти препятствия не остановили Магеллана, хотя и потребовали немало усилий и времени для их пусть даже не полного устранения.
Наконец основные приготовления были завершены, и 10 августа 1519 года флотилия из пяти каравелл отошла от причала Севильи и направилась вниз по Гвадалквивиру к порту Санлукар-де-Баррамеда. Здесь в ожидании подходящей погоды парусники бросили якоря и пробыли на стоянке более месяца. Большая часть этого времени, однако, была потрачена на замену вновь обнаруженных гнилых запасов продовольствия и пополнение его недостачи, так как Магеллан отказывался отправляться в дальнее плавание при таких условиях. 24 августа глава экспедиции, у которого за полгода до этого родился сын, подписал свое завещание, согласно которому он оставлял часть своего немалого наследия своей жене, их ребенку, своей сестре и двоюродным родственникам, а другую передавал нескольким монастырям и церквам в Испании. Перед самым выходом в море Магеллан направил письмо-меморандум королю, в котором он вновь выражал свое убеждение, что Острова Пряностей, включая самые богатые специями Тернате и Тидоре, открытые его приятелем Серрану, находились в зоне владения Испании. Во вторник 20 сентября 1519 года флотилия из пяти приведенных в полный порядок каравелл покинула берег Испании и взяла курс на юго-запад. Никто из отплывавших или среди остававшихся на берегу людей не предполагал, что это будет самым далеким и самым продолжительным плаванием из всех совершавшихся в истории человечества.
Экспедиция Магеллана состояла из флагмана «Тринидад», капитаном которого был сам глава экспедиции, а также парусников «Сан-Антонио» с заменившим Фалейру (он все-таки был помещен в дом умалишенных) капитаном Хуаном де Картахеной, «Консепсьон», которым командовал Гаспар Кесада, «Виктория», во главе которой стоял Луис де Мендоса, и самого небольшого из них «Сантьяго» под руководством капитана Жоау Серрану. Несмотря на основные мирные цели флотилии, она была довольно сильно вооружена. Помимо приданной артиллерии на ней размещались 62 тяжелых и 10 легких пушек-фальконетов, а также 50 аркебуз. Помимо этого они везли сотни пик, алебард и мечей вместе с личными офицерскими кольчугами, латами и шлемами с султанами, а также несколько сот арбалетов и множество длинных луков. Благодаря стараниям Магеллана парусники были хорошо оснащены самыми современными тогда навигационными приборами, картами, книгами по навигации и 18 песочными часами. В трюмах находились ящики с обменным товаром, заполненные стеклянными бусами, колокольчиками, медными браслетами, рыбными крючками, немецкими ножами, маленькими зеркальцами, рулонами самых разных ярких тканей и прочей мелочью. Кроме того, в них везли запасы специальных подарков для султанов, правителей и вождей, с которыми планировалось налаживать политические и торговые отношения.