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

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

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

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

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

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

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

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

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

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