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