Летом 1511 г. Альбукерке захватывает Малакку, город, который португальцы по праву считали ключом к Китаю. Магеллан сражается и под стенами Гоа, и в Малакке. Однако никакой награды за свои боевые подвиги он не получает. Альбукерке не склонен жаловать угрюмого и смелого в суждениях воина, нередко позволяющего себе открытую и резкую критику мероприятий и планов вице-короля.

В 1511 г. Магеллан участвует в экспедиции Антониу де Абреу, посланной из Малакки к Молуккским островам. Флотилия Абреу дошла до островов Банда, где в изобилии произрастали мускатные орехи. Скупив огромное количество орехов, Абреу поспешил возвратиться в Малакку. Только один корабль под командой Франсишку Серрана отправился дальше, к Молуккским островам. Серран высадился на острове Тернате, родине лучшей в мире гвоздики, и здесь надолго обосновался, сделавшись советником местного султана. С Серраном Магеллан состоял затем в переписке. Мы увидим дальше, что сведения, полученные Магелланом из Тернате, оказались для него далеко не бесполезными.

Между тем на целых два года следы Магеллана теряются. Арагонский историк XVI в. Архенсола сообщает, что Магеллан побывал на каких-то островах, расположенных в 600 лигах (т. е. около 3000–3500 км) от Малакки. Будучи там, он переписывался с Серраном, который якобы звал его к себе на остров Тернате.

Один из испанских историков XVI столетия, Овьедо, указывает, что Магеллан, отправляясь в свое знаменитое плавание, оставил в Главном архиве Индий записку, в которой упоминалось о его пребывании в Восточных Индиях и на Островах Пряностей.

Неизвестно, однако, побывал ли он в этих краях сам или собрал о них сведения, находясь в Малакке. Бесспорно, что в конце 1513 г. Магеллан появляется в Португалии.

Его сбережения погибли: их присвоили себе наследники одного португальского купца, с которым вел торговые дела Магеллан. Его родовое поместье было разорено. Магеллан снова поступает на военную службу и сражается в Марокко. Он становится жертвой интриг собственных соратников и, несмотря на отвагу, проявленную в боях, не только не получает благодарности, но и навлекает на себя немилость командующего португальской армией. Король отказывает ему в пенсии, темные слухи о бесчестных сделках с «маврами» сопутствуют Магеллану после его возвращения из Марокко.

Вероятно, в 1515–1516 гг., вернувшись в Лиссабон, Магеллан разработал свой проект плавания юго-западным путем к Островам Пряностей. Этот проект был категорически отвергнут королем Мануэльм, и Магеллан оставил Португалию. 20 октября 1517 г. он прибывает в Севилью, с тем, чтобы осуществить свой замысел на службе у испанской короны.

В Севилье Магеллан попадает в колонию португальских эмигрантов. Он знакомится здесь с комендантом севильской крепости Алькасар, старым португальским воином Диогу Барбозой, и с его сыном Дуарте, впоследствии участником кругосветного плавания.

На дочери Диогу Барбозы Магеллан женится в 1518 г. В Севилье он встречает своего старого знакомого португальца-астронома Руй Фалейру, одного из лучших картографов того времени, и продолжает совместно с Фалейру разработку своего проекта. Диогу Барбоза рекомендует Магеллана видному должностному лицу Индийской торговой палаты Хуану де Аранде. Начинаются долгие переговоры об осуществлении проекта Магеллана.

В Испании заморские экспедиции, как правило, организовывались на паевых началах короной и частными лицами. Король по рекомендации Индийского Совета заключал договор (асьенто) с предпринимателем, предложившим проект экспедиции. Казна обязывалась оказать материальную поддержку предпринимателю, предоставляла ему права наместника (аделантадо) в новооткрытых территориях и долю в ожидаемых барышах. Однако корона специальными пунктами договора ограничивала юрисдикцию наместника-открывателя и связывала все его действия, поскольку каждое мероприятие лица, стоящего во главе экспедиции, контролировалось особыми чиновниками, назначаемыми Индийским Советом.

При этом в большинстве случаев судьба таких открывателей оказывалась плачевной. Воспользовавшись их услугами, корона прибирала к рукам новооткрытые территории, а организаторы заморских предприятий годами обивали пороги Индийского Совета и королевской приемной, тщетно пытаясь восстановить свои права. Коронные казуисты всегда толковали договорные обязательства казны в аспекте, не благоприятном для истца, и нередко случалось, что человек, открывший на испанской службе богатейшие земли, умирал в нищете. Таков был финал деятельности Колумба.

Когда Магеллан начал хлопоты о своем проекте, вести о дальнейших португальских успехах на Востоке и о бедственном положении испанских колоний в Новом Свете как нельзя более благоприятствовали осуществлению его замысла. Но не так-то легко было добиться официального одобрения проекта. В 1516 г. на престол вступил шестнадцатилетний внук короля Фердинанда Карл Габсбург, впоследствии император Священной Римской Империи, вошедший в историю под именем Карла V.

Молодой король прибыл в Испанию из Фландрии, где он провел детские и отроческие годы. Он привез с собой советников-фламандцев, но они не пользовались в Испании популярностью и плохо разбирались в испанских делах. Менее всего они были озабочены проектами заморских экспедиций; все их внимание приковано было к Германии, где близкая кончина престарелого императора Максимилиана сулила тяжкую борьбу за корону.

Между тем проект должен был рассматривать королевский совет, в котором министры-фламандцы оказывались в большинстве.

Аранда, после долгих споров с Магелланом и Фалейру выговоривший себе восьмую долю в грядущих прибылях предприятия, заинтересовал проектом Хуана де Фонсеку, президента Индийского Совета. Это был влиятельный сановник, четверть века ведавший делом организации дальних экспедиций и управления новооткрытыми территориями. Фонсека отстаивал интересы короны, абсолютно не считаясь с претензиями открывателей, знания и энергию которых он умел, однако, великолепно использовать.

Аранда также заинтересовал проектом Магеллана богатого купца и опытного организатора морских экспедиций Кристоваля де Аро, который обещал щедрую материальную помощь.

В марте 1518 г. в Вальядолиде, городе, где за 12 лет до этого умер Христофор Колумб, королевский совет рассмотрел проект Магеллана и Фалейру.

Король и его фламандские советники отнеслись холодно к их предложениям. Однако по настоянию Фонсеки совет одобрил проект, и 22 марта король подписал первые указы об организации экспедиции.

Проект Магеллана и Фалейру основывался на двух предпосылках, в истинности которых они были твердо убеждены. Во-первых, составители проекта считали, что Южно-Американский материк уходит на запад, подобно тому как африканская земля у мыса Доброй Надежды уходит на восток, и что, следовательно, где-то за 40° ю. ш. должен быть проход, ведущий из Атлантического океана в Южное море. Магеллан показал глобус, на котором в том месте, где должен был находиться пролив, расплылось белое пятно. Это пятно он нанес, опасаясь, что португальские шпионы проведают об истинном местоположении пролива. Во-вторых, Магеллан и Фалейру полагали, что Молуккские острова расположены сравнительно близко от Южной Америки: на 136–138° в. д. (на самом деле острова эти лежат между 127° и 129° в. д.), в «испанской зоне» земного шара. Подобно всем своим современникам, авторы проекта ошиблись в оценке длины экваториальной окружности Земли. Магеллан считал ее равной 37000 км, т. е. приуменьшал более чем на 3000 км ее протяженность.