4月13日，船队从蒙巴萨北上，路上拦截了一条阿拉伯船，并俘获了十几个人。4月14日船队进泊南纬3度的马林迪。葡萄牙人在马林迪港见到了配备有大炮的奇怪的船，船员的相貌也与阿拉伯人不同，褐色的皮肤，留着长长的胡须和头发。经过交往，得知他们是印度人。当地苏丹和穆斯林对葡萄牙人比较友好，这点与莫桑比克与马林迪的统治者和摩尔人不同。达·伽马通过苏丹还请到了一位引水员伊本·马季德。此人生于阿曼的阿拉伯—伊斯兰著名航海世家，也有人说他是印度古吉拉特人。他用阿拉伯文编写过航海方面的一些著作，其中重要的为《关于航海的科学基础及其规则的有益材料录》和《马季德的三本（被发现的）航海笔记》。船队4月24日从马林迪起锚升帆开始了横渡印度洋的最后航行。船队由马季德领航，沿着他熟悉的航线向东北行进。他还带有一张用摩尔人方法画的表现整个印度海岸的地图。他们乘印度洋顺路的西南季风，经过24天的航行，便顺利走过了3000多千米的航程。5月17日，他们看到了印度海岸。5月18日，他们在卡利库特以北约50英里的马拉巴尔海岸停靠。1498年5月28 日，达·伽马船队进泊卡利库特港(今科泽科德)，葡萄牙人终于来到了几十年来孜孜以求的真正的印度，几代人为之不懈努力的新航路终于打通了。对印度来说，这也是它中世纪以来第一次接待来自欧洲白人基督教世界的船队。所以葡萄牙人在卡特库特立起了第三根石柱。

“最后，每只船上只剩7、8个人还能工作，但都已很不健康。而且，如果这种情况再持续两周，我们不是全部死去，便是再退回到印度去。须知我们已到了这样的地步，即不管什么纪律都已不复存在了……但是，最后，上帝赐福给予了顺风。好像到了第6天，我们望见了陆地”

卡特库特是个古老的小王国，这里的居民所信奉的印度教称为萨穆林，意即山和海的主人。历代萨穆林都鼓励海外贸易。在这里，如果买卖成功，则只交纳1/40的关税，否则可以不缴。卡利库特的外贸和商业主要掌握在穆斯林手中，其中有外来的阿拉伯人、波斯人，也有本地人改宗伊斯兰教的。自然，居民中本地的印度教徒更多。不过，达·伽马一行却把当地的印度教教徒、神庙、神祇当成了基督教教徒、教堂、圣母。

卡特库特达·伽马登陆纪念碑。1498 年 5 月 27 日，达·伽马率领 170 名船员从这里登陆。这一脚踏上来，改变了印度近代史的走向。当地居民并不关心这座纪念碑的历史价值。它已经被包围在附近住户的院里。村民进出院子门需要躲闪它，纪念碑显得有些碍事。

达·伽马先派一个囚犯上岸进城打探。第二天该罪犯带回一个北非摩尔人穆斯林。那人一上船就用卡斯提尔语（即西班牙语）大声打招呼：“好运气！真是好运气！这里有许多红宝石、祖母绿！你们真应该感谢造物主帮你们来到这个遍地财富的国度！”。葡萄牙人因此更加兴奋。达·伽马一行最初受到当地统治者友好的接待。达·伽马呈上了国书，献上了帽子、珊瑚珠、布匹、金属锅等一般的礼品，但没有一件被看得起。因为当时印度的文明程度不亚于西方，卡利库特的萨穆林又是很富有的君王。葡萄牙人在卡利库特进行交易，但他们的货物销路很有限，又受到穆斯林的抵制和敌视。达·伽马本人甚至也曾被穆斯林扣留了几天后才逃出，险遭暗算。当地的一个突尼斯人蒙凯德会说西班牙语，他告诉达·伽马还有暗杀他的阴谋。8月上旬，达·伽马等准备离去，但又不愿交纳关税。卡特库特当局便扣押了葡萄牙人的一些货物和几个船员；达·伽马竟抓了十几个卡利库特人。后来萨穆林放了葡萄牙人并退还了货物，但达·伽马仍扣留了人质。

8月29日，达·伽马船队离开卡利库特向北驶去。曾向葡萄牙人通风报信的蒙凯德因在当地呆不下去了而随船去葡。卡特库特萨穆林因葡萄牙人欠税和带走几名人质便派出一支舰队追击。双方在海上曾发生交火，但达·伽马船队凭着火力强大仍得以逃脱。船队到了卡纳诺尔，受到友好对待，进行了商业贸易。9月20日葡萄牙人在果阿附近的安吉迪夫岛抛锚停泊时与几只船遭遇。达·伽马以为是卡特库特的追击者，便下令开炮，并抢了一艘船，船上的人乘小船逃走。10月初，船队离开了安吉迪夫岛，开始了重渡印度洋的航行。由于不顺风，又失去了马季德的帮助，船队在印度洋上走走停停，或走大Z字形航线，拖了近3个月。其间许多人得了坏血病，其中一些人死去。所以这段航行竞成了葡萄牙人探航西非以来，甚至是地理大发现开始以来最困苦的航行。让我们看看当事人描写的可怕景象：“我们逗留在海上，总共差3天就是3个月，因为常常碰到无风和逆风而无法航进。我们大家生着重病，牙床肿得很厉害，以致全部牙齿被包住，因而不能吃东西。脚也浮肿起来，身上又长了大脓疮。这些脓疮使健壮的人即使没有什么别的病，也变得虚弱以致死去。因此，在此期间死去了30人(另有30多人早已死去)。最后，每只船上只剩7、8个人还能工作，但都已很不健康。而且，如果这种情况再持续2周，我们不是全部死去，便是再退回到印度去。须知我们已到了这样的地步，即不管什么纪律都已不复存在了……但是，最后，上帝赐福给予了顺风。好像到了第6天，我们望见了陆地”。

1499年1月初，船队到了今索马里的阿拉伯—伊斯兰城邦摩加迪沙。达·伽马不问青红皂白便炮击一通，没有进港。1月9日，船队回到了友好的马林迪(今属肯尼亚)，又受到友好接待。特别是吃上了新鲜蔬菜和水果，解除了坏血病的威胁和痛苦。葡萄牙人在此立下了第四根石柱。在马林迪休整数日后，船队继续南航。很快驶过了抱有仇恨情绪的蒙巴萨(今也属肯尼亚)，没有进港。之后由于减员和物资耗尽，达·伽马又被迫丢弃和烧毁了一艘船，把货物和人员转移到别的船上。船队继续航行，避开了莫桑比克港，在此附近，他们立下了最后一根石柱。3 月20日，船队绕过了好望角。一个月后，因为遇到风暴，达·伽马的旗舰与另一艘船走散了。那艘船在库埃霍的指挥下于1499年7月10日首先返回里斯本。4月25日，达·伽马航行到几内亚一带时，维尔霍的日记结束了。不知他是病了还是死了，或是觉得没什么值得记录的。在最后的大西洋航程里，达·伽马的哥哥、船长之一保罗·达·伽马病了。达·伽马改变了航向，驶向亚速尔群岛的特塞拉岛。上岸后的第二天达·伽马的兄长便死去。达·伽马让旗舰先回里斯本，自己留下来料理后事。8月底，旗舰圣布里埃尔号驶进里斯本湾。9月9日，达·伽马乘快艇返抵里斯本。至此，人类有史以来最远的一次航行胜利结束，生还者仅55人。