若い頃のことはほとんど分かっていない。1580年ころにポルトガル北部ミーニョ地方のポンテ・ダ・バルカで生まれたとされている。1492年から王妃レオノーラの小姓として弟ディオゴとともに仕えたらしい。その翌年コロンブスが新大陸から帰っている。ヴァスコ・ダ・ガマがインドから帰った時は19歳だった。
1505年インドに向かうフランシスコ・デ・アルメイダが率いる21隻の艦隊に「王家の受給者」として若いフェルナン・デ・マガリャンイス（マゼラン）と弟ディエゴ・デ・ソウサが乗り込んでいた。二人とも月給1000レアルだった。艦隊は10月21日インドのカナノールに着いた。
1506年11月にヌノ・ヴァス・ペレイラが率いる艦隊がアフリカのソファラ要塞の支援に向かい翌年10月インドのコチンに戻った。この航海にマゼランが参加していた。
1509年2月アルメイダはディウ沖の海戦で、マムルーク・グジャラート・カリカットの連合艦隊を破りインド洋支配を強めた。この戦いでペレイラは死亡し、マゼランは負傷した。3月には新しい後継総督アフォンソ・デ・アルブケルケがコチンに着いていた。
1508年4月リスボンを出港したディオゴ・ロペス・デ・セケイラの4隻の艦隊が1509年4月コチンに着いた。その艦隊はマラッカ遠征の為に派遣されたものでコチンで70人を募り、8月マラッカに向かった。この中にマゼランとフランシスコ・セラーンが入っていた。
9月にマラッカに着くと始めは友好的だったが、イスラム商人の警告などもあって攻撃を受けた。そのときに上陸していたポルトガル人の多くを残したまま、1510年1月コチンに戻った。
マラッカでフランシスコ・セラーンを救うためにマゼランは決断力と行動力を示したらしい。

1510年コチンを出た2隻の船がモルディヴ沖で座礁した。このときマゼランは救命ボートに上級船員を乗せ、救援のボートの派遣を依頼して自らは水夫と共に船に残った。10月アルブケルケはゴア攻撃について「王の軍司令」を集めて意見を求めている。このときにマゼランも発言している。1月にマラッカから戻ったときにマゼランとセラーンは「カピタン」となったらしい。
1510年1月アルブケルケは基地を作るためにカレクートを攻撃して大敗した。2月にはゴアを占領することができて、そこに要塞を築いた。
1511年アルブケルケは交易用の綿布を大量にカナノールで仕入れ、18隻の艦隊にポルトガル兵800人とマラバル兵200人以上を乗せてマラッカに向かった。マラッカは捕虜の解放には応じたが、それ以上の譲歩はしなかったため、アルブケルケはマラッカを攻撃し8月に攻略した。その後直ちにビルマやタイに使節を派遣している。彼らの恐怖心を抑え、食糧の確保を図る必要があった。また12月にはアントニオ・デ・アブレウ、フランシスコ・セラーン、シマン・アフォンソ・ビザグドをそれぞれ別の船でモルッカ諸島に向かわせた。ポルトガルの兵士の多くはマラッカ防衛のため1年以上この海域に止まっていた。
スペインの海峡探索の動きを知ったマヌエル王はマラッカ、モルッカ諸島に早く到達するように急がせていた。マラッカ攻略に参加したマゼランはエンリケというマライ人の奴隷を与えられた。このエンリケは後にフィリピンで通訳として活躍した。
モルッカ諸島に着いたのはセラーンの船だけだった。困難を極めた航海だったためセラーンはモルッカ諸島が実際よりもかなり東にあると考えたらしい。彼の手紙はマゼランにも届いた。このことがマゼランに西回りの航海を考えさせたともされる。
マゼラン　世界周航　マゼラン2　海峡を探すスペイン