1519年8月10日，船隊從塞維利亞啟航，駛向瓜達爾基維爾河口-聖盧卡爾灣。皮加費塔的日記從這天開始。9月20日船隊進入大西洋。船隊先駛向西屬加那利群島，9月26日到達加那利的聖克魯斯島。在加那利期間，麥哲倫收到嶽父的一封信，提醒他注意西班牙船長們可能的搗亂，因為已有風聲透露出來。10月3日，船隊離開加那利駛向西南方的佛得角群島，這時船隊中的反麥分子開始活動起來。因為當時從歐洲到美洲既可走哥倫布開辟的西班牙航線，也可走卡伯拉爾開辟的葡萄牙航線。走後一條航線似乎要在海上多漂泊些日子，但卻可利用赤道洋流和東北信風的順風順流。況且他們的任務之一是探尋南美地區通向大南海的海峽或南美洲的盡頭，所以直接去南美還可以縮短整個航期。麥哲倫主張走這一條葡萄牙航線，為此與船隊中的反麥分子進行了鬥爭，甚至把聖安東尼奧號船長卡爾塔海納扣押起來，另派德·科卡代理船長。
經過兩個月的海洋漂泊，戰勝了連續一個月的暴風雨，船隊於11月29日到達巴西海岸累西非（伯爾南布科）。船隊在稍事休整後迅速南下，於12月13日進入裏約熱內盧灣。船隊在這裏略做休整，補充淡水和新鮮給養，與當地印第安人進行不等價交換。皮加費塔寫道，“這個地方的人拿五六隻火雞換一把刀子或一個魚鉤，一對野鵝換一把梳子。用一麵小鏡子或一把剪刀所換的魚，足夠10個人吃一頓……在意大利玩的那種撲克牌的一張王牌，他們用5隻火雞同我換。”這位編年史家記述的當地瓜拉尼印第安人吃人的習慣，聽了令人毛骨悚然。他們“吃他們的敵人的肉，這並不是因為好吃，而是一種風俗習慣。他們並不把抓來的人一次吃光，而是一塊一塊地吃。他們把人剁成塊，在煙筒裏烤幹，每天切下一小塊，同家常便飯一起吃，以此提醒自己記住敵人。”
12月26日，船隊離開裏約熱內盧灣，於次年（1520年）1月10日來到拉普拉塔河河口。這條南美第二大河，極其寬闊的河口乍看起來真像一個海峽的人口。但經過探航才知道它是流向大西洋的大河河口。麥哲倫非常失望，但他不露聲色，率隊繼續南下。從此他們進入文明人類未曾航行過的水域了。
2月3日，船隊到達他們稱之為巴伊奧德洛斯帕托斯（即企鵝灣）的地方。探險者在那裏第一次發現了企鵝，這種企鵝後來被命名為麥哲倫企鵝。它們是廣泛分布於整個南極洲的企鵝科鳥類最北邊的代表。船隊繼續前進，2月24日，船隊在約南緯41度處發現海岸走向突然由南轉西，很像一條海峽或南美的盡頭。他們沿海岸向西前進了約250公裏，才發現它隻是一個普通的海灣即聖馬蒂亞斯灣。進入3月份，南半球南部已是秋涼，天氣日漸寒冷，越益晝短夜長。寒冷的南風從南極迎麵吹來，航行十分困難。3月31日，船隊駛人南緯49度今阿根廷南部聖胡利安港。麥哲倫決定在此過冬。這一帶比較荒涼、杳無人煙、補給困難。為了做過冬的長期準備和應付新出現的危機，麥哲倫下令縮減口糧，大量獵禽捕魚貼補。但也隻維持到1521年3月便斷糧了。不管怎樣，縮減口糧漁獵補貼的決定是英明的，否則探險隊熬不過在太平洋上的百日航行。
天寒地凍、杳無人煙、給養匱乏，加上幾次探索海峽或大陸盡頭都沒有成功，這一切使許多船員灰心失望，不安的情緒籠罩著船隊，許多人要求返航。船隊中的反麥分子便利用這種沉鬱氣氛策劃叛逃。4月1日夜，康塞普遜號船長凱薩達、被撤去船長職務的卡爾塔海納率領30人偷襲了聖安東尼奧號，綁架了新船長麥斯基塔，殺害了二副，占領了該船。維多利亞號船長門多薩也參加了叛亂。這樣，5條船中的3條已被叛亂分子控製，遠航似乎快夭折了。但機智勇猛、身經百戰的麥哲倫卻沉著冷靜，力挽狂瀾，出奇製勝。他利用與叛亂分子談判的機會，派保安官埃斯皮羅薩率人乘小艇去維多利亞號佯裝談判，登船後突然把門多薩刺死，迫使叛亂分子投降，控製了維多利亞號。麥哲倫隨即將維多利亞號、特立尼達號和聖地亞哥號一字排開，停泊在港灣的出口，堵住兩條叛亂船的逃路。4月3日淩晨，凱薩達欲率聖安東尼奧號奪路逃跑，向旗艦衝擊，並命令開炮，但無人聽命。麥哲倫命令特立尼達號鳴炮警告，並喊話勸降。聖安東尼奧號船上被脅迫的船員願意繼續追隨麥哲倫遠航。麥哲倫派人乘小艇去把凱薩達等幾個為首分子逮捕。最後一艘叛亂船康塞普遜號及其叛亂船長卡塔爾海納見大勢已去，第二天也隻好投降。