当时的西班牙，为了维护本国的经济利益，加强与葡萄牙争霸海洋的实力地位，急需在哥伦布发现“新大陆”之后继续寻找西航通向东方的新航路。因为，西班牙的一些有识之士认为，亚洲东部地区，特别是摩鲁古群岛，依据“教皇子午线”的规定，应属于西班牙的势力范围，对此西班牙国王极为关注。但为了避免与葡萄牙的争端，向西航行是惟一的办法。因此，哥伦布发现“新大陆”后，西班牙也纷纷派远征船队试图绕过“新大陆”，登上那梦寐以求的香料群岛。然而，一次次都失败了。广袤的大陆像一堵不可逾越的天然屏障，横躺在远航者的面前，使他们乘兴而去，失望而归。
正在这时，麦哲伦在他岳父的帮助下，很快于1518年3月18日觐见了国王。麦哲伦向国王呈献了标有自己所拟定航线的十分详尽的彩色地球仪，并认为香料群岛应属于西班牙。由于他的计划与当时西班牙的国策不谋而合，国王极为赞赏，当即批准了他的计划，答应为他装备一支远航舰队。
麦哲伦万万没有想到他的计划能如此顺利地被西班牙国王采纳，心里有说不出的高兴。但他也同样没有想到，一场破坏性的阴谋也将开始了，这给他后来的航行带来了很多麻烦。
就在国王同意麦哲伦西航计划之际，突然，葡萄牙的一位极富有的福格尔家族的代理人德亚罗，带着几袋金币和近年来葡萄牙海外发现的秘密文件星夜赶来，说和国王闹翻了，并代表福格尔家族答应供给西班牙大批补助金，目的是推荐一位葡萄牙流亡海员哥米什担任远航队的指挥官。
德亚罗的建议使西班牙国王很为难，于是，德亚罗做出让步，支持麦哲伦的计划，但坚持要哥米什充当旗舰上的主舵手。对此国王欣然同意。
1518年3月22日，由西班牙国王、德亚罗和麦哲伦三方签署了远航协定：麦哲伦向西航行到达摩鲁古群岛；若航行成功，授予麦哲伦及其后代担任新发现的一切地区与岛屿的总督职务；新发现地区内全部收入的二十分之一归麦哲伦所有；政府准备5艘船和船员，以及两年用的粮食。
麦哲伦被任命为远征队的司令。出航的准备工作历时18个月，这主要是葡萄牙国王和外交官从中干扰的结果。得到密令的葡萄牙外交官向西班牙国王示意：麦哲伦不忠于自己的祖国，也不会忠于其他国家。这致使西班牙国王起了疑心，先限制了拨给他的人数，后又派官员监视他的行为。与此同时，外交官私下劝麦哲伦，大讲西航的危险，让他放弃计划。麦哲伦态度坚定地说：“我不需别人的劝告，我自己知道该怎么做。”
外交官见劝说不成，便卑鄙地进行暗中破坏。他用大量金钱贿赂各处，使船上装有许多发霉的面粉、糖和发臭的咸牛肉，又唆使西班牙贸易局的人为麦哲伦收购破旧不堪的5艘船。他仔细看过后，觉得用这5只“漂浮的棺材”去远航，肯定是会喂鲨鱼的。他还嫌不够，千方百计派奸细混入远航队伍，伺机进行破坏，甚至叛乱。那个哥米什，就是一个密探。
这些阴谋活动，麦哲伦一点也不知道。1519年8月，一切准备就绪。船队由5只船组成：“特利尼达”号（麦哲伦的旗舰）、“圣安东尼奥”号、“康塞普尼翁”号、“维多利亚”号、“圣地亚哥”号，都是破旧船只，麦哲伦把它们改造得能经得起这次远航的考验。招募船员也费了很大的周折。一些高傲的西班牙船员不愿在外籍司令领导下工作；一些职业海员也不敢参加这为期两年的远航。麦哲伦煞费苦心终于招齐了250人，其中，大部分是西班牙人，也有葡萄牙水手和意大利、法国、德国、希腊、马来西亚等15个国家和地区的船员。这支混杂的队伍使麦哲伦遇到了许多麻烦。
启航前，麦哲伦回到了塞维利亚，拥抱了他心爱的正怀身孕的妻子和宝贝儿子，便匆匆离去，谁知这竟然是一场永别。
1519年9月20日，麦哲伦兴致勃勃地登上旗舰，升起了指挥旗。在一片欢呼声中，船队驶出桑卢卡尔港，开始了人类历史上一次划时代的远航。
发现麦哲伦海峡
麦哲伦船队离港后，向南直奔加那利群岛，在那里补充了淡水和供应品。正待启航时，忽见一只轻帆驶来，说要面见麦哲伦。原来，那些葡萄牙奸细的家属泄露了在航行中进行破坏，甚至杀死麦哲伦的消息，他的岳父得知后立刻派人送信，提醒他随时提高警惕，严防手下的船长捣乱。信中提到几个奸细的名字，特别提到“圣安东尼奥”号船长卡尔塔海纳。看了来信，麦哲伦大惊失色，但马上又镇静下来，装出若无其事的样子。
10月3日，船队离岛继续沿非洲海岸南行。为了把这个人员复杂的船队熔炼成纪律严明的适于远航的集体，麦哲伦命令各船白天看他的船旗，夜晚看他的船灯，紧随航行。每天日落时各船长须向旗舰靠拢，向其欢呼致意。为此，麦哲伦坚持每天晚上在船尾甲板上点一把火把，作为“信号灯”。还制定了信号灯语言：挂两盏灯，表明在改变航向；挂三盏灯，意味着减帆；挂四盏灯，是必须落下所有的帆……这种命令和服从关系，自然使其他船长的权限受到了挑战。
然而，以“圣安东尼奥”号船长卡尔塔海纳为首的一伙奸细，无视麦哲伦的领导，伺机生事。船队绕过塞拉利昂后，遇上了逆风恶浪，同时鲨鱼也跟随不舍，接着又是1个月的暴风骤雨，整个船队处于惊涛骇浪之中，随时都有危险发生的可能。险情过去，船队进入了赤道无风带，船只裹足不前，加之酷热的天气，船员中开始出现怨言。卡尔塔海纳趁机借事挑衅，麦哲伦在忍无可忍的情况下，立即扣押了他，并撤消其船长的职务，交给“维多利亚”号船长缅多萨看管，任命经验丰富的西班牙水手麦斯基塔为船长。
反对派的气焰暂时被压下去了，船队顺利行进。1月29日，渡过大西洋，到达南美的巴西海岸。他们在里约热内卢湾过了两周田元诗般的陆地生活，补充了淡水和供应品，修理了船体和船帆。
12月26日，船队依依不舍地离开里约热内卢湾南行，去寻找那渴望已久的海峡。两星期后，他们发现了一条很宽的向西去的水道，它正好处于地图上标示的这个海峡可能存在的地方。
但这条水道越弯越窄，很快成了一条河流，即今天的拉普拉塔河。大失所望的麦哲伦认定这是地图画错了，这个海峡一定在更南的地方，可能在南方大陆的冰冻地区。
许多船员由于失望而要求返航，麦哲伦却坚决不后退。船队继续迎接险恶的风浪和阵阵冰雹驶向南半球，准备在那里度过秋天和冬天。麦哲伦每一觉只能睡上一两个小时，像其他船员一样，一连几个星期吃不上一顿热饭。3月底，麦哲伦出于对船员们的同情，决定上岸过冬，船队驶进了阿根廷南端的一个当今称为圣胡利安的海港。6个月来，他们劈恶浪，斗风雨，仍未找到海峡，换来的惟有恶劣的气候，灰色的山崖和寒冷，荒凉的海滩。这里既没有植物，也没有野兽，麦哲伦不得不下令减少每日口粮，节约食品。这一切不利的条件，使船员们的情绪普遍低落。
船队中的反对派，利用船员的低落情绪，趁机要求恢复粮食定量，或调转船头返航，或返回温暖的拉普拉塔河过冬。所有的要求都被麦哲伦严词拒绝，并坚定地宣布：除非死亡，不然他就要履行誓言，按国王的命令，一直航行到找着一定存在的海峡为止。于是，一次蓄谋已久、欲置麦哲伦于死地的哗变终于爆发了。为首的还是卡尔塔海纳，他于4月1日晚控制了3只船，想冲出海港，返回西班牙。
转眼间，麦哲伦献身了多年的事业，有可能付诸东流。面对如此紧张的局势，麦哲伦镇定自若，以迅雷不及掩耳之势，果断地平息了这次叛乱，夺回了对整个船队的控制权，紧张的气氛很快就过去了。麦哲伦立即实施了军法审判，处以凯萨达首恶分子极刑，砍头肢节4块挂到港口4个显眼的地方示众。卡尔塔海纳和一个闹事的牧师被永远放逐在这个荒凉的海湾。同时，赦免了应判死刑的40多人，以保证日后航行的顺利进行。由于麦哲伦的宽恕，这些人感恩戴德，后来忠实追随麦哲伦，患难与共。叛乱平息了，麦哲伦的远航探险事业没有半途而废，这一切均归功于麦哲伦的足智多谋、随机应变的本领和不屈不挠的精神。
漫长、阴暗的严冬还未过去，麦哲伦便命令“圣地亚哥”号向前航行考察沿岸一带。不幸的是，这只船在一次风暴中沉没，好在只有一人淹死，幸存的37人在干旱贫瘠的风蚀草原上流浪4天后获救。他们向麦哲伦报告说发现了一个更好的海港。于是8月底，剩下的4只船驶向新港，在那一直呆到10月18日。
这时南半球的春天即将来临，麦哲伦急不可待地又开始去寻找这难以捉摸的海峡。3天后，船队驶进一个宽阔的海湾，这里潮水很大，且不见有淡水。麦哲伦命令“圣安东尼奥”号和“康塞普尼翁”号先行侦察。他们在忽宽忽窄、曲折迂回的水上迷宫中探航了100多英里，断定已不再是一个河口后，高兴地调转船头，向麦哲伦报告。顷刻间，船队沸腾了，船员们疲惫的脸上露出了笑容。于是，整个船队扬帆航行在两岸高山之间。