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