1519年8月10日，船隊離開塞維利亞港，前往桑盧卡爾港（Sanlúcar），他們將在那裏離開大陸。麥哲倫同他的嶽父迪奧古·巴爾波查及妻子和繈褓中的兒子道別，轉身奔向岸邊等待的船隻。
一、艱難的尋找
9月20日，船隊正式啟航進入大西洋。此前，老巴爾波查派人給他送來可靠消息：船隊中的西班牙船長們領有特別任務，他們將不會唯麥哲倫之命是從。麥哲倫早已想好應對之策，那就是“絕對權威”原則。他規定：白天，所有船都必須依據旗幟的指示航行；夜晚，所有船必須跟從旗艦上的燈火指示行動。每天夜幕降臨之前，所有船隻都必須向旗艦靠攏，所有船長都必須親自向海軍上將致敬。任何違反規定的行為都要受到極其嚴厲的懲罰。
9月26日，船隊到達加那利群島的聖克魯斯島（Santa Cruz），這是最後一塊熟悉的土地。離開聖克魯斯島，麥哲倫指揮旗艦改變了向西直航的既定航線，把船頭轉向西南，由於這一改變，西班牙船長們與麥哲倫發生了首次衝突。西班牙人的首領卡爾塔海納要求麥哲倫解釋改變航線的理由。麥哲倫決定借此機會樹立自己的“絕對權威”。他冰冷地拒絕了卡爾塔海納的要求，並向所有人宣布：他將獨自指揮船隊，任何人無權要求他做出解釋。羞憤的卡爾塔海納沒有服軟，他不再按照規定每天向麥哲倫致敬。
卡爾塔海納公然違抗命令的行為並沒有激起麥哲倫的反擊，他展示出奇異的沉默。他不與任何船長交流，每天都獨自佇立、思考。事實上，他醞釀著一次行動。很快，機會來了，一名船員犯了錯，麥哲倫以征詢懲罰意見為由召集4名船長來到旗艦。卡爾塔海納也來了，他的目的不是要處理船員犯錯的事情，而是再次向麥哲倫質問改變航線的原因。麥哲倫依舊保持沉默。卡爾塔海納不依不饒地繼續逼問，兩人的對峙達到頂點，這或許正是麥哲倫想要的結果。他命令警衛將卡爾塔海納逮捕，並告訴他：“你現在是我的階下囚”，隨即又宣布撤銷他的全部職務。麥哲倫的態度堅決，行動果斷，使其他西班牙人個個膽戰心驚，這招殺雞儆猴的手段取得成功。麥哲倫任命安東尼奧·德·科卡（Antonio de Coca）取代卡爾塔海納為“聖安東尼奧號”的船長，船隊又恢複了紀律。[5]不久，麥哲倫任命自己的表弟麥斯基塔取代科卡擔任船長，完全控製了這艘最大的船隻。