1517 年，落魄的麦哲伦来到西班牙，住在老巴尔博扎的家里。老巴尔博扎曾到印度做过生意，后因对葡萄牙政府不满而移居到西班牙的塞维利亚，身居要职。他的儿子巴尔博扎是葡萄牙驻印度总督阿尔布克尔克的译员和秘书，到过马六甲及苏门答腊北部一带。1516 年，巴尔博扎从印度返回葡萄牙航行途中， 根据自己所搜集的资料写成了一部手稿《东方纪事》，手稿并没有出版，只是以抄本的形式流传。
《东方纪事》的内容主要讲述从好望角开始直到太平洋西部边缘的各国概况，包括中国和琉球。这也成为麦哲伦了解东方的一手资料。在西班牙，老巴尔博扎不仅热情接待了麦哲伦，还把自己的一个女儿嫁给了他。为了使麦哲伦能够实现远航的目的，老巴尔博扎还利用自己的人脉使麦哲伦获得西班牙一些官员与商人的支持，并有机会把他引荐给西班牙国王。
当时，西葡两国的海外殖民况争十分激烈。麦哲伦向西班牙国王呈献了绘制得很详尽的彩色地球仪，上面标有他所拟定的航线，他向国王说明这条航线的优点，避开了葡萄牙人控制的非洲航线，可以同样到达盛产香料的马鲁古群岛。
有了西班牙国王的加持，1519 年 8 月，麦哲伦组建成 5 艘载重一百来吨的小型船和约 270 人的远航探险队，8 月 10 日，从西班牙塞维利亚启航沿河顺流而下，9 月 20 日，离开瓜达尔基维尔河河口启航。他们这次远航的目的，不仅是星辰大海，还有神秘东方的黄金和香料。
发现太平洋
1520 年 1 月 12 日，麦哲伦率领船队进入拉普拉塔河口，他满怀希望能在纬 40°附近找到列什波亚“发现”的那个“海峡”，然而在恶劣的气候条件下，他从拉普拉塔湾至圣胡立安海湾，整整花了两个月时间，仍没有找到“海峡”的踪迹。这时，他才明白那些有关“海峡”的新闻原来并不靠谱。也意味着法利罗的全部计算和他自己的论断显然是错误的。如果没有海峡，这次远航必定是无功而返，于是，以凯萨达、卡尔塔海纳和缅多萨为首的一批船员揭竿而起，要求返航。但麦哲伦坚信海蛱的存在，他坚决镇压了要求返航的叛乱，并宣告：除非死亡，不然他就要履行誓言，一直航行到找着一定存在的海峡为止。
10 月 21 日，历经艰辛与曲折的麦哲伦船队，终于在南纬 52°突出的海岸处发现了一个新的海峡。这个海峡并不是平直的坦道，而是迂回曲折、深浅不一、沟壑纵横的迷官。经过海峡时，麦哲伦见海峡南岸有土著人升起的烟火，就称南岸之地为“火地”，后夹确定南岸之地是座大岛后，便命名为火地岛。麦伦伦运用熟练的航海技术，指挥船队经过 28 天的艰苦探索，终于在 1520 年 11 月 28 日走出了长达 560 公里、蜿蜒曲折、充满危?的海峡（后来被称为麦哲伦海峡），进入了巴尔博亚 1513 年穿过巴拿马地峡时发现的浩瀚的陌生大洋“南海”。
这时，最初的 5 艘船只剩下 3 艘了，一艘船在探航时沉没，还有一艘船脱离了船队，径自返回西班牙去了，剩下的 3 艘船绕过了美洲最南端的海角，进入茫茫的太平洋中。他们先沿今阿根廷海岸北上了一段，大约在南纬 35°处，即今智利尔卡一带离开海岸，然后向西偏北开始了横渡。远航途中一直风平浪静，没有遇到任何风暴、台风、暴雨等。船员们因此把“南海”改称“太平洋”。
船队中，有一位意大利维琴察小贵族皮加费塔随行并充当马来语翻译，他在旗舰“特立尼达”号上写的环航日记被保存下来。他在日记中写道：“我们在这三个月又十天中航行了约 4000 里格（1里格 =3.18 海里，相当于 5.556 公里），穿越了一片广袤的海洋即太平洋。说真的它很平静，因为在此期间我们没有遭遇任何风暴。”皮加费塔还感慨地说：“如果不是上帝和圣母给予我们如此好的天气，我们本来将全都饿死于那片超广袤的海洋之中。”
在横渡太平洋的航程中，船队发现了后来所称的大小两个麦哲伦星云。皮加费塔在环航日记中写道：“南极不像北极那样星光灿烂，这里看到许多星星聚集成群，就像两朵云雾。它们之间的距离不远，井且暗淡无光。在这些星群中有两个巨大的星团，但不十分明亮，移动得也很缓侵。”接下来，“当我们到达太平洋中心时，我们在西方看到一个由五颗星组成的十字架，非常明亮，互相规整地对应排列着挂在天上。”一般认为，他们发现的是南十字（星）座。今日澳大利亚、巴布亚新几内亚和萨摩亚的国旗上也都有南十字座，新西兰的国旗上则有省略了 e 星的南十字座。
饥饿、焦渴和坏血病
在享受征服星辰大海喜悦的同时，水手们也经历着痛苦的煎熬，这就是饥饿、焦渴（缺干净淡水引起）和坏血病。皮加费塔记道：我们…陷入了太平洋中。我们己经有三个月又ニ十天没有吃过任何新鲜食物了。我们吃饼干，其实那些东西已不成其为饼干，而是爬满蠕虫的渣屑，因为虫子已把好的啃光了。而且它还发出一股鼠尿臭。我们喝的是黄水，因备储存过久，（太阳晒热而）臭得令人作呕。我们也以牛皮充饥，这些牛皮本来是覆盖在桅桁之上以防磨损帆索之用的。由于风吹日晒雨淋，已经非常之硬。我们先把牛皮浸在海水里四五天，再在余火灰烬上烤一会，然后オ吃。我们常吃木头锯末。老鼠的价格是每只半个杜卡特金币，但那时连老鼠都买不到了。而各种不幸中接下来的是最糟糕的，我们有些船员的上下齿龈都肿了起来，怎样也无法吃东西，因此活活饿死。死于这种病的有十九人。在此期间有二十五或三十个人病倒了，他们的手臂、腿部或其他地方浮肿瘀血起来，以致只有少数人身体还保持良好。
皮加费塔这里所说的是一种特殊的远航病，即坏血病，又称维生素 C 缺乏症，因长期吃不到新鲜食物特别是新鲜蔬菜水果所致。经过漫长的 98 天在无人区的航行和短暂滞留后，船队终于发现了陆地，来到了今马里亚纳群岛有人烟的岛屿。1521 年 3 月 5 日来到一个岛，麦哲伦取名拉丁帆岛，并进行了初步的淡水补给。3 月 6 日，船队又抵达附近较大、人烟较稠的关岛停靠补给。
当时关岛土著查英罗人还处于原始社会阶段，看到船队后，他们烽拥而至，爬上航船哄抢、拿走欧洲人船上的东西，甚至还拖走了旗舰“特立尼达”号上的小艇。西班牙人因此称这一带为“盗贼群岛。麦哲伦下令武力讨伐。他率领 40 名武装船员登陆征剿，射杀了 7 个土著人，烧了四五十间茅屋和土著人的一些小船，抢了一些新鲜食物，补充了一些洁净淡水，并夺回了小艇。当地人没有见过弓箭，皮加费塔说“当我们用弩箭射中任何一个这些人的腰部并完全射穿时，他们都要审视着，把箭杆从这一边拉到另一边，大为惊奇地拔出来，接着就倒下死去。”
这次船队到达关岛并登陆补给新鲜蔬菜水果等至关重要。否则的话，坏血病会进一步加重和蔓延。那么，即使能横渡成功，代价也更大。不过，他们射杀当地土著居民，烧毁房子和小船也成为这次环球航行中的污点。