Неизвестно, однако, побывал ли он в этих краях сам или собрал о них сведения, находясь в Малакке.
Бесспорно, однако, что в конце 1513 г. Магеллан появляется в Португалии.
Его сбережения погибли: их присвоили себе наследники одного португальского купца, с которым вел торговые дела Магеллан. Его родовое поместье было разорено. Магеллан снова поступает на военную службу и сражается в Марокко. Он становится жертвой интриг своих же собственных соратников и, несмотря на отвагу, проявленную в боях, не только не получает благодарности, но и навлекает на себя немилость командующего португальской армией. Король отказывает ему в пенсии, темные слухи о бесчестных сделках с маврами сопутствуют Магеллану после его возвращения из Марокко.
Вероятно, в 1515–1516 гг., вернувшись в Лиссабон, Магеллан разработал свой проект плавания юго-западным путем к Островам Пряностей.
Этот проект был категорически отвергнут королем Мануэлем, и Магеллан оставил Португалию. 20 октября 1517 г. он прибывает в Севилью с тем, чтобы осуществить свой замысел на службе у испанской короны.
В Севилье Магеллан попадает в колонию португальских эмигрантов. Он знакомится здесь с комендантом севильской крепости (Алькасара), старым португальским воином Дьогу Барбозой и с его сыном Дуарте, впоследствии одним из участников кругосветного плавания.
На дочери Дьогу Барбозы Магеллан женится в 1518 г. В Севилье он встречает своего старого знакомого португальца астролога Руй Фалеру, одного из лучших картографов того времени, и продолжает совместно с Фалеру разработку своего проекта. Дьогу Барбоза рекомендует Магеллана видному должностному лицу Индийской торговой палаты Хуану де Аранде. Начинаются долгие переговоры об осуществлении проекта Магеллана.
В Испании заморские экспедиции, как правило, организовывались на паевых началах короной и частными лицами. Король, по рекомендации Индийского Совета, заключал договор (асьенто) с предпринимателем, предложившим проект экспедиции. Казна обязывалась оказать материальную поддержку предпринимателю, предоставляла ему права наместника (аделантадо) в новооткрытых территориях и долю в ожидаемых барышах. Однако корона специальными пунктами договора ограничивала юрисдикцию наместника-открывателя и связывала все его действия, поскольку каждое мероприятие лица, стоящего во главе экспедиции, контролировалось особыми чиновниками, назначаемыми Индийским Советом. При этом в большинстве случаев судьба таких открывателей оказывалась плачевной. Воспользовавшись их услугами, корона прибирала к рукам новооткрытые территории, а организаторы заморских предприятий годами обивали пороги Индийского Совета и королевской приемной, тщетно пытаясь восстановить свои права. Коронные казуисты всегда толковали договорные обязательства казны в аспекте, не благоприятном для истца, и нередко случалось, что человек, открывший на испанской службе богатейшие земли, умирал в нищете. Таков был финал деятельности Колумба.
Когда Магеллан начал хлопоты о своем проекте, вести о дальнейших португальских успехах на Востоке и о бедственном положении испанских колоний в Новом Свете как нельзя более благоприятствовали осуществлению его замысла. Но не так-то легко было добиться официального одобрения проекта. В 1516 г. на престол вступил шестнадцатилетний внук короля Фердинанда Карл Габсбург, впоследствии император Священной Римской Империи, вошедший в историю под именем Карла V.
Молодой король прибыл в Испанию из Фландрии, где он провел детские и отроческие годы. Он привез с собой советников-фламандцев, но они не пользовались в Испании популярностью и плохо разбирались в испанских делах. Менее всего они были озабочены проектами заморских экспедиций; все их внимание приковано было к Германии, где близкая кончина престарелого императора Максимилиана сулила тяжкую борьбу за корону.
Между тем проект должен был рассматривать королевский совет, в котором министры-фламандцы оказывались в большинстве.
Аранда после долгих споров с Магелланом и Фалеру, выговоривший себе восьмую долю в грядущих прибылях предприятия, заинтересовал проектом Хуана де Фонсеку, президента Индийского Совета. Это был влиятельный сановник, четверть века ведавший делом организации дальних экспедиций и управления новооткрытыми территориями. Фонсека был верным цепным псом короля Фердинанда и отстаивал интересы короны, абсолютно не считаясь с претензиями открывателей, знания и энергию которых он умел, однако, великолепно использовать. В трагических судьбах Колумба и Бальбоа не последнюю роль сыграл этот облаченный в епископскую сутану канцлер заморского приказа.