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

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

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

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

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

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

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

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

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

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

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

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

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

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

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