1509年9月、回復したマゼランはペレイラ率いるマラッカ遠征に加わった。この時点でポルトガルは胡椒を除く多くの香料の産地がインドではなく香料諸島であること、ライバルであるスペインが西回りルートでの東洋航路を模索していることなどを把握し早期の香料諸島の覇権を急ぎ、まずは香料諸島への重要な中継拠点であるマラッカの確保に乗り出した。しかしポルトガルにとって最初のマラッカ遠征であるペレイラの艦隊はマラッカ王の策略によって大敗する。この敗戦のなかでマゼランは水際で戦い危うい状況であった従兄弟セラーンをボートで救う活躍をしている[17]。ポルトガルの最初のマラッカ遠征は失敗に終るものの、遠征中の業績によってマゼランは船長の位を授かることになる[18]。家柄で地位が決まることの多い中世で、下級貴族出身ながら見習い士官から船長の地位にまで上ったマゼランの船乗りあるいは戦士としての能力は相当に高かったものと想像されている。

インドの沿岸拠点の支配を固めたポルトガルは1511年4月、再度マラッカに大艦隊を送りこれを制圧する。このポルトガルのマラッカ制圧戦の功績でマゼランは指揮する大型のカラベラ船の1隻と個人的な奴隷（マラッカのエンリケ）を与えられた。引き続いて、ポルトガルは香料諸島への遠征隊を派遣する。この香料諸島遠征隊にはマゼランは参加していなかったものの従兄弟のセラーンが参加している[19][20]。
セラーン

マゼランの従兄弟であり、同じ東洋派遣部隊の将校であるフランシスコ・セラーンはポルトガルの最初の香料諸島遠征に参加したが、艦隊は途中で遭難。セラーンは孤立しながらも通りかかった中国のジャンク船を奪い香料諸島に到達する[21]。セラーンは香料諸島において島の一つテルナテの王の軍事顧問のような役割をはたし、王の重臣として高い地位と裕福な生活を手に入れる。セラーンは香料諸島に王につぐ地位を持ち滞在しながら、ポルトガルやマゼラン宛に手紙を書き報告している、マゼランにあてた手紙でセラーンは「香料諸島がうわさ通り豊富な香料を産する」ことと、「テルナテ王のポルトガルへの好意とポルトガル側の香料諸島確保の意思の一致にもかかわらず、ポルトガルの支配がまだ確立できていない」ことを知らせ、そして私はヴァスコ・ダ・ガマが見たよりもより豊かで、大きく、より美しい新世界を発見した。あなた（マゼランのこと）がここで私と一緒になり、私のまわりにある喜びを自ら味わうことを望む ? イアン・カメロン(1978)、p.34

とマゼランに書き送っている。セラーンの手紙によって香料諸島の事情を知ったマゼランだが、これはのちにマゼランがスペイン王の元で西回りの香料諸島渡航ルート開拓を志願する動機の一つとなっている。セラーンはこの後、マゼランがスペインから西回りの東洋航路発見の航海についている間に香料諸島の王の1人ティドーレ王にテルナテ王と共に計略で毒殺されている[22][23][24]。ポルトガル人マゼランを失ったスペインのマゼラン艦隊が香料諸島にたどり着いたとき、セラーン及びテルテナ国王は8ヶ月前にすでに毒殺されており、マゼラン艦隊は香料諸島の別の島の王であるティドーレ王のもとで厚遇を得る[25]。

1511年のマラッカ制圧の後、1年半ほどはマゼランが何をしていたのかは記録はない。おそらくはマラッカ周辺海域の哨戒任務についていたのではないかと推測されている。マゼランは1513年1月に帰国するが、帰国した訳も分かっていない[26]。およそ8年の東洋艦隊勤務で船乗りとしても戦士としても十分な経験を積んでの帰国であった[26]。
1513年のポルトガルの情勢

バスコ・ダ・ガマが初めて喜望峰回りのインド航路を開いた1499年からマゼランが帰国した1513年までのわずか14年の間にポルトガルは安定したインドへの航海ルートを確立していた。マゼランが8年の勤務を終え帰国したポルトガルは香料貿易が栄え、16世紀まで香料貿易を独占していたヴェネツィアからその地位を奪い大海洋国(ポルトガル海上帝国)としての地位を固めていた。香料貿易を独占し遠洋貿易を独占する勢いのポルトガルにはヨーロッパ中の有力商人とくにイタリア商人とドイツ商人とが取引を希望してその商権を争う状態であった[27]。ドイツの大商人であるフガー商会はその代理人としてクリストバル・アロをリスボンにおいていた。クリストバル・アロは優れた商人であり、バスコ・ダ・ガマの喜望峰回りのインド航路発見以前、コロンブスの新世界発見の直後から西回りでのアジアへの航海ルート探索に関心を持っていた。アロはポルトガルが開拓している喜望峰回りでの東洋交易の詳細も把握し、インド交易に多額の投資を行うのに加え、アロは自身がスポンサーとなり西回りの東洋交易ルート開拓の探検隊を派遣するまでになっている。しかし、アロはイタリア人商人の中傷によってポルトガル王マヌエルの信任を失い、1516年スペインに活動の場を移す。アロは後に1519年からのマゼランの世界周航に大きな役割をはたすことになる[28]。
マゼランの北アフリカ遠征

1513年にポルトガルに帰国したマゼランがその後何をしていたのかは記録が少なくよくはわかっていないが、帰国後ほどなく1513年8月にはポルトガルの北アフリカ征服の一環であるモロッコのアザムール攻略に参加し、最前線で戦士として戦い戦傷を受け右足が不自由になっている。後年の研究者はマゼランは騎士として正々堂々とした戦闘を好む性格であったのであろうと推測している[注 5][29]。こののちマゼランは鹵獲品管理担当将校になるが、鹵獲品管理担当将校という役職は私腹を肥やすことが可能な役職であったためにマゼランは言われ無き中傷と嫉妬にさらされ、鹵獲品の横流しで私腹を肥やしたとあらぬ疑いをかけられている[30]。鹵獲品の横流しの汚名を着せられたマゼランは無断で帰国、ポルトガル王マヌエルに無実を訴え、香料諸島への派遣を直訴するが、王はこれを無視し、モロッコへ戻るよう命令する。一旦、北アフリカに戻されたマゼランは疑惑がうやむやの内にポルトガルに帰国する[31]。後年の研究者達はマゼランの性格と行動からマゼランへの汚職の告発はおそらくは冤罪であろうと推測している[32][33]。
ポルトガル宮廷を去る

1515年、北アフリカ遠征から帰ったマゼランはポルトガル王マヌエルに謁見し、その後ポルトガル宮廷を去っている。マゼランがポルトガル宮廷を去った詳細や理由についての確実な資料はないが、通説では、マゼランはポルトガル王に2つの依頼をし、拒絶されたからだと推測している[34]。