计划拟定好了，如何实施呢？身无分文的麦哲伦，惟一的办法便是要争取王室的支持。
尽管麦哲伦遭到过葡萄牙国王的奚落，但为了实现宏伟计划，他不得不走这条路。不利的是，国王正满足于达·伽马开辟的新航路不断从印度掠来财富和取得更多的殖民地，而对这种新计划的航行结果所能带来的好处信心不足。再说，由于葡萄牙和西班牙两个国家争夺殖民地，已于1494年签订了一条条约，规定了一条“教皇子午线”，线以东为葡萄牙势力范围，线以西为西班牙控制。这样，全部非洲和亚洲在葡萄牙势力范围内，有辽阔的土地可掠夺，不必向西航行，引起争端。因此，他的西航计划遭到国王的拒绝。
绝望中的麦哲伦认为，他不会从葡萄牙获得任何支持，便愤然带着西航计划，希望在西班牙实现自己的理想。
当时的西班牙，为了维护本国的经济利益，加强与葡萄牙争霸海洋的实力地位，急需在哥伦布发现“新大陆”之后继续寻找西航通向东方的新航路。因为，西班牙的一些有识之士认为，亚洲东部地区，特别是摩鲁古群岛，依据“教皇子午线”的规定，应属于西班牙的势力范围，对此西班牙国王极为关注。但为了避免与葡萄牙的争端，向西航行是唯一的办法。因此，哥伦布发现“新大陆”后，西班牙也纷纷派远征船队试图绕过“新大陆”，登上那梦寐以求的香料群岛。然而，一次次都失败了。广袤的大陆像一堵不可逾越的天然屏障，横躺在远航者的面前，使他们乘兴而去，失望而归。
正在这时，麦哲伦在他岳父的帮助下，很快于1518年3月18日觐见了国王。麦哲伦向国王呈献了标有自己所拟定航线的十分详尽的彩色地球仪，并认为香料群岛应属于西班牙。由于他的计划与当时西班牙的国策不谋而合，国王极为赞赏，当即批准了他的计划，答应为他装备一支远航舰队。
麦哲伦万万没有想到他的计划能如此顺利地被西班牙国王采纳，心里有说不出的高兴。但他也同样没有想到，一场破坏性的阴谋也将开始了，这给他后来的航行带来了很多麻烦。
就在国王同意麦哲伦西航计划之际，突然，葡萄牙的一位极富有的福格尔家族的代理人德亚罗，带着几袋金币和近年来葡萄牙海外发现的秘密文件星夜赶来，说和国王闹翻了，并代表福格尔家族答应供给西班牙大批补助金，目的是推荐一位葡萄牙流亡海员哥米什担任远航队的指挥官。
德亚罗的建议使西班牙国王很为难，于是，德亚罗做出让步，支持麦哲伦的计划，但坚持要哥米什充当旗舰上的主舵手。对此国王欣然同意。
1518年3月22日，由西班牙国王、德亚罗和麦哲伦三方签署了远航协定：麦哲伦向西航行到达摩鲁古群岛；若航行成功，授予麦哲伦及其后代担任新发现的一切地区与岛屿的总督职务；新发现地区内全部收入的二十分之一归麦哲伦所有；政府准备5艘船和船员，以及两年用的粮食。
麦哲伦被任命为远征队的司令。出航的准备工作历时18个月，这主要是葡萄牙国王和外交官从中干扰的结果。得到密令的葡萄牙外交官向西班牙国王示意：麦哲伦不忠于自己的祖国，也不会忠于其他国家。这致使西班牙国王起了疑心，先限制了拨给他的人数，后又派官员监视他的行为。与此同时，外交官私下劝麦哲伦，大讲西航的危险，让他放弃计划。麦哲伦态度坚定地说：“我不需别人的劝告，我自己知道该怎么做。”
外交官见劝说不成，便卑鄙地进行暗中破坏。他用大量金钱贿赂各处，使船上装有许多发霉的面粉、糖和发臭的咸牛肉，又唆使西班牙贸易局的人为麦哲伦收购破旧不堪的5艘船。他仔细看过后，觉得用这5只“漂浮的棺材”去远航，肯定是会喂鲨鱼的。他还嫌不够，千方百计派奸细混入远航队伍，伺机进行破坏，甚至叛乱。那个哥米什，就是一个密探。
这些阴谋活动，麦哲伦一点也不知道。1519年8月，一切准备就绪。船队由5只船组成：“特利尼达号”(麦哲伦的旗舰)、“圣安东尼奥号”、“康塞普尼翁号”、“维多利亚号”、“圣地亚哥号”，都是破旧船只，麦哲伦把它们改造得能经得起这次远航的考验。招募船员也费了很大的周折。一些高傲的西班牙船员不愿在外籍司令领导下工作；一些职业海员也不敢参加这为期两年的远航。麦哲伦煞费苦心终于招齐了250人，其中，大部分是西班牙人，也有葡萄牙水手和意大利、法国、德国、希腊、马来西亚等15个国家和地区的船员。这支混杂的队伍使麦哲伦遇到了许多麻烦。
启航前，麦哲伦回到了塞维利亚，拥抱了他心爱的正怀身孕的妻子和宝贝儿子，便匆匆离去，谁知这竟然是一场永别。
1519年9月20日，麦哲伦兴致勃勃地登上旗舰，升起了指挥旗。在一片欢呼声中，船队驶出桑卢卡尔港，开始了人类历史上一次划时代的远航。