在当时要实施一个庞大的远洋探险计划，没有国家的支持是很难得以实现的。麦哲伦决定随身带去里斯本国王宝库里的珍贵资料，向西班牙国王提供航海情报，同时报告经法利罗计算的“香料群岛”，不属于葡萄牙管辖范围，而是在教皇划归西班牙版图的消息，说明“香料群岛”是属于西班牙的财产。这样，麦哲伦把世界上最富饶的群岛和通往该岛的最短的航路资料，呈献给西班牙国王查理五世，这就是远洋探险计划容易获得西班牙国王支持的原因。
麦哲伦自愿加入西班牙国籍，为别国服役，甚至改名换姓（由费迪南德·麦哲伦扬什，改名为费迪南德·麦哲利扬涅斯），这将是多么昂贵的代价啊！然而为了实现伟大的理想和一生的抱负，又何乐而不为呢？何况历史上远航探险家哥伦布、卡博特、卡达英斯塔和维斯普奇也有类似之举。
麦哲伦的等待、忍耐、思索已告结束。经过一阵阵痛苦之后，一个伟大的行动终于产生了。1517年10月20日，他把胆怯的伙伴法利罗暂时留在葡萄牙，便和跟随他多年而形影不离的奴仆亨利，一起来到了西班牙的塞维利亚。12月中旬法利罗也来到了这里。
塞维利亚城位于西班牙南部的达儿微河畔，是一座繁华而美丽的海港城市，建筑宏伟，街道整洁，人口不多，是通往新印度的门户，大多数西行的船只，都是从瓜达尔基维尔河两岸出发。这里商人、船长、经纪人和代理人云集。因此，国王下令在塞维利亚设立了专门的“商务院”、“印度院”负责内藏商人和航海家的所有报告、地形图和札记。“商务院”（Casa de contratacion，建立于1503年），接待来往旅客。“印度院”既是商品交易所，又是船只经营处。凡是探险者打算悬挂西班牙国旗进行新的探险，就必须先取得“印度院”的允许和支持。
由于塞维利亚城靠近葡萄牙，所以有不少葡萄牙人移居这里。其中要塞司令迪奥古·巴尔波查一家就是从葡萄牙移居这里的侨民。巴尔波查已担任要塞司令职务14年了。此人是最受全城尊敬的人，是圣地亚哥勋章的获得者。他对这个新来乍到的葡萄牙航海家，接待十分热情。早年，巴尔波查曾在印度洋航行过，这可能是与麦哲伦一见如故的重要原因。他儿子杜亚脱·巴尔波查继承了父亲的事业，遍游印度、波斯和马来西亚水域，写过一本记述东方国家的书籍——《杜亚脱·巴尔波查文集》，后来成为麦哲伦航海探险的成员之一。
巴尔波查热情好客，请麦哲伦住在家里。不久，他的女儿俾脱利兹对这个37岁的麦哲伦表示了爱慕之情。1518年两位有情人终成了眷属。从而使麦哲伦在塞维利亚得到了地位和靠山。他虽然在葡萄牙失去了一切公民的权利，失去了宫廷的微薄薪水，但如今在西班牙却得到了更多的补偿。他有巴尔波查的关心和支持，又有妻子的陪嫁，现在可以毫不犹豫地跨进“印度院”的大门了。
一个人的成功，往往来自于自身的坚持与智慧，加上多方面的努力与求得周围人们的支持。麦哲伦自从来到西班牙筹备远航探险以来，通过各方求助，取得了辉煌的胜利。他找到了一个支持他事业而且温柔的妻子，结识了许多支持他的朋友，遇到了些可以保护他的大人物，得到了国王的信任。
麦哲伦与好友法利罗得到“印度院”主管胡安德·阿朗大的推荐，在西班牙北部法拉多利城（当时西班牙王宫所在地）觐见国王。当时的西班牙国王是出生于德国神圣罗马帝国哈有斯堡家族的查理一世。稍后，查理一世又当选为德国神圣罗马帝国的皇帝，号称查理五世。除德国、西班牙外，查理在西欧还有领地，他的权势是相当大的。
1518年3月18日，查理国王接见了麦哲伦。麦哲伦向国王呈献了绘制得相当详尽的彩色地球仪，上面还标出了他拟完成的航线，并向国王保证，不侵犯葡萄牙国王的领土或海洋，在“新大陆”南端找寻通向“香料群岛”的海峡，最后到达生产东方香料的岛屿——“香料群岛”。
麦哲伦的远航探险计划很快得到了查理五世的赞同。王宫里的许多大人物，例如：大主教方萨加等，也尽力支持。由于当时西班牙海外远征事业的规定：必须由国王和私人合股经验。所以，一个庞大的远洋探险计划必须经国王和私人签署协定后才能生效。
1518年3月22日，查理五世和麦哲伦、法利罗签署了协定。这份文件是这样开头的：
“鉴于你们，葡萄牙王国公民、骑士费迪南德·麦哲利扬什和葡萄牙王国公民、学士路易·法利罗，自愿为我国效劳，在我们管辖之海域内服役，为此，特同你们签署如下协定。”
协定用宫廷行为中惯用的辞藻和语言，详细写道：
“尔等应在划归我们管辖的范围之内，竭力发现新海域，如若尔等前往该地探险，届时另有其他人染指其间，致使尔等蒙受损失，此乃不义之举，朕绝不允许，为此特颁布指令如下：今后十年之内，任何人不得沿同一航路前去开拓尔等选定的地域。如若有人拟操此业，请示国王批准，则必于应诺之前，事先通告尔等。尔等可与其他开拓者一样，在同一时期使用同样装备的同等数量之船舰，独自完成大业。”
协定规定：授予麦哲伦和法利罗担任将来在航海中所发现的一切地域和岛屿的总督的职务，并可传给子孙，把所发现地区内的全部收入（包括利润和捐税等）的二十分之一留给他们。协定中还规定，如果将来发现的岛屿超过六个时，麦哲伦和法利罗就有权在这六个以后，所发现的岛屿中选两个，获得当地全部收入的十五分之一。这就是说，发现的土地越多，发现者的好处也就越多。
国王答应装备五艘议定吨位的船只，两年内保证充分供应船只所需的全体船员、粮食和火炮。这一具有历史意义的文件，以下面的庄严语句结束：“关于上述各项，我以自己的荣誉和国王的觐见担保，我将下令按照本文所述严格履行每一条款，因此特命令制定此协议书，并由我亲自签字。”
此外，还颁发了一项特别指令，下达到西班牙各级政府机关和官员，将协定通知他们，以便在各方面给麦哲伦和法利罗以交代。
协定签署以后，年轻的查理五世国王催促早日装备好舰船，尽早出发。他每周都要过问进程，只要准备工作遇到障碍，他就下谕令，排队阻难。在国王陛下的关照下，麦哲伦被封为海军上将，圣地亚哥勋章（宗教骑士勋章，设立于12世纪，获此勋章的骑士曾参加过同摩尔人的战争）的获得者。从此，他握有生杀大权，成为舰队的统帅。
