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

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

Летом 1511 года новый губернатор Алфонсо де Албукерке посылает группу парусников во главе с Антонио Абреу на завоевание столь стратегически важной Малакки, Магеллан принимает участие в этой экспедиции и в осаде Малакки, которая сдалась португальцам через полтора месяца. Заняв таким образом твердую опору неподалеку от заветных островов, Албукерке, не теряя времени, снаряжает на разведку к ним небольшой отряд из трех каравелл под командованием того же Абреу, а капитанами двух других стали друзья Магеллан и Серрану. В конце 1511 года они успешно достигают Амбона и Банды — двух островов с невероятным обилием очень дорогого в Европе мускатного ореха. Полностью загрузив каравеллы этим богатством, португальцы отправились в обратный путь в Малакку. Но отставшее судно Серрану в дороге наткнулось на рифы и было совершенно разбито. Однако находчивому другу Магеллана удалось хитростью овладеть искавшим его пиратским судном и не только восстановить свой драгоценный груз на Амбоне, но и обогатить его новыми специями на одном из самых богатых пряностями островов — Тернате. Распорядившись своим потрясающим приобретением как настоящий негоциант, отправив его в Лиссабон, сам Серрану остался на полюбившемся ему Тернате в качестве неофициального представителя Португалии. Оттуда он успешно вел свои коммерческие дела и писал восторженные письма Магеллану о невероятных богатствах окружавших его островов в гвоздике, корице и мускатном орехе, а также об их экзотических красотах, великолепном климате и беззаботной жизни их приветливых обитателей. Экспедиция капитанов Абреу, Серрану и Магеллана положила начало эпохе процветания Португалии за счет обогатившей ее торговли дорогими в Европе специями с далеких восточных островов.

Тем временем у Магеллана созревал очень важный план открытия более простого пути к Островам Пряностей через Атлантику на запад, чем далекое, трудное и опасное плавание вокруг мыса Доброй Надежды и через Молукский пролив. По его собственным ознакомительным наблюдениям и по более продолжительному опыту своего друга Серрану он знал, что эти острова с мусульманским и языческим населением были крайне заинтересованы в очень выгодной для них торговле с европейцами. Но путь к ним через Атлантику по маршруту Колумба требовал нахождения пролива через американский континент, который вот уже на протяжении двух десятилетий безуспешно искали испанские и португальские мореплаватели. Теперь Магеллан решил попытаться это сделать сам.

При возвращении в Лиссабон он окончательно отработал свой план и в ожидании удобной возможности представить его королю Дону Мануэлю отправился добровольцем с португальской армией в Марокко. При поездке оттуда в Лиссабон для разбирательства армейского инцидента с королем Магеллан воспользовался этим случаем представить монарху свой план поиска нового пути к Островам Пряностей, но получил отказ: Португалия уже владела монополией на обогащавшую ее торговлю с Островами Пряностей по маршруту вокруг Африки, а две уже предпринятые попытки капитана Коэльу найти пролив через новый континент в Южное море Бальбоа окончились безрезультатно.

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

В это время королем Кастилии, Леона и Арагона уже почти год был 17-летний Карл Первый, вступивший на престол после смерти своего деда Фердинанда. Но уже в июне следующего года он избирается королем Священной Римской империи до коронования его императором в Риме после двух предстоявших лет. Однако папа римский дал согласие, чтобы он пользовался императорским титулом и ритуалом сразу. С того времени испанский король Карл Первый становится императором Священной Римской империи Карлом Пятым. Именно от его решения теперь зависела судьба смелого проекта нового испанского подданного Фердинанда Магеллана.

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

Аранда выполнил свое обещание и в начале 1518 года вместе с Магелланом и очень обиженным на последнего Фалейру встретился с Карлом Пятым в Вальядолиде. В то время никто не имел точного представления о размерах Южного моря, и Магеллан, опираясь на догадки ведущих географов и картографов, в изложении своего проекта монарху убеждал его, что Острова Пряностей находятся всего в нескольких сотнях миль от побережья Панамы. 8 марта 1518 года молодой император подписал контракт по реализации плана Магеллана. Он назначил его и Фалейру совместно генерал-капитанами армады с щедрым жалованием и обещал им наследственные титулы аделаотадо в тех новых землях, которые они откроют, если они не принадлежали христианским государям Король согласился предоставить им пять каравелл с около 250 офицерами и членами экипажей, распорядился предоставлять им одну пятую прибыли экспедиции и дал обещание не посылать в течение 10 лет каких-либо конкурентов по их маршруту.