在此期间，达·伽马还从两位来访的土著首领的衣着和交谈中，敏锐地意识到这里已受到某种高度发达的文明的影响，如果不是印度，就是离此不远的阿拉伯国家了。他的精神为之一振，信心大增，胜利在望。丰富的知识，敏锐的观察和联想，大胆的推理，是达·伽马航海探险成功的又一个重要原因。
1498年2月底，船队重新出航，不久就进入非洲东岸莫桑比克海峡多暗礁险滩的区域，达·伽马一行只好白天行船，晚上停泊，以免黑夜搁浅。3月2日，船队终于驶出莫桑比克海峡，远处的海边有个大港湾，达·伽马决定去那儿暂时歇脚。
海港慢慢地靠近了，一派新的景象渐渐地呈现在眼前，浓绿色的森林无声无息地远去了，隐匿在鲜花盛开、翠绿叶丛之中的白色小屋慢慢地出现了，远处的清真寺也隐约可见。他们来到了深受阿拉伯文化影响的穆斯林城市——莫桑比克。
岸上突然涌出许多阿拉伯人，他们吹着长喇叭，诵着《古兰经》，欢迎达·伽马一伙人的到来。显然，阿拉伯人误把他们当作穆斯林兄弟了，达·伽马将计就计，默默地接受了阿拉伯人的欢迎。
莫桑比克的土著居民主要是黑人，但在13世纪时被阿拉伯人征服。嗣后，阿拉伯人垄断了这里的全部贸易，并带来了伊斯兰文化，当地绝大多数居民皈依了伊斯兰教，成为穆斯林。达·伽马派人拜访了当地酋长，后者祝他们一路顺风。水手们在港内发现了许多来自印度的商船，满载金、银、丁香、珍珠和宝石。葡萄牙人好不嫉妒，当地穆斯林告诉他们，这些东西在印度到处都有，俯拾即是，根本不值钱。此时达·伽马开始意识到今后真正的对手将是阿拉伯人，他们是比暴风浓雾和逆流更危险的敌人。不久，阿拉伯人也发现他们是异教徒，了解到他们去印度的真正目的，就把他们当作敌人看待了。城里居民对他们的态度马上变得冷漠起来，上岸采购货物和装取淡水的水手成为不受欢迎的人，被公开驱赶。达·伽马恼羞成怒，下令炮击岸上的人群，以掩护水手们安全返船。关系彻底恶化，葡萄牙人感到必须离开此地，以防不测。他们抢了附近几条船上的财物，抓了两个莫桑比克的阿拉伯人做领航员，火速起锚出海。阿拉伯人的武装船只追了过来，但毕竟敌不过葡萄牙人猛烈的炮火，先进武器的威力又一次显示出来了。
虽然莫桑比克的追兵被击退了，但洋流和风向却不利于北上，而且在莫桑比克抓到的阿拉伯领航员还有意捣乱，在航途中欺骗水手，谎称群岛为大陆。达·伽马觉得前程更加险恶，命令水手们备加小心，下令严刑拷打了说谎的领航员。为了获得航路的一些确切情况，水手们随后又捕获一艘当地小商船，达·伽马亲自拷问了船主——一个可怜无辜的阿拉伯老头。
船队小心谨慎地前进，现在除了要与恶劣的天气作斗争外，还要对付更可怕的阿拉伯对手。蒙巴萨到了，该城是非洲东岸最大的阿拉伯港口城市，位于岩石遍布的半岛上，这里地形复杂，气候炎热。备尝艰辛的达·伽马由于对阿拉伯人和穆斯林心怀戒备，再加上水手们精疲力竭，不敢贸然入港，就在公海抛锚。据后来获得的情报，这次真够险的了，原来阿拉伯领航员和莫桑比克方面早有密谋，准备在他们进蒙巴萨港时，有意领船触礁。达·伽马的处事沉着冷静又一次挽救了船队的命运。
蒙巴萨的首领已接到莫桑比克人的通知，得知了葡萄牙人的行踪，他认为这伙人不仅是异教徒，而且是自己未来商业上的强大竞争对手，决心趁早除掉他们。首领知道，他无法在公海上打败装备精良、作战经验丰富的葡萄牙舰队，达·伽马的船队不进港，须引诱它进港。首先，首领派人给达·伽马一行送去羊、桔子、柠檬和甘蔗，后又赠予黄金和宝石，并邀请舰队入港。达·伽马表面接受了邀请，但暗底下命令水手们保持警惕，以防意外。
第二天，当舰队准备启程前进时，忽然发生两船相撞事故，接着船上的阿拉伯人纷纷跳入大海，或躲了起来，跳入大海的马上就被附近的阿拉伯船只救走。见此情景，达·伽马什么都明白了，暴跳如雷的他将在莫桑比克抓到的两个领航员严刑拷打，然后下令作好战斗准备。巡逻的水手突然听到船的周围有水响的声音，原来阿拉伯人偷袭来了，一些人正在割缆绳，另一些已经爬上甲板。巡逻者马上发出警报，等到水手们拿着武器出来时，阿拉伯人早已撤退，隐蔽在不远处的小船上。葡萄牙人随时可能遭到蒙巴萨人的进攻，水手们惊恐不安，天一亮，达·伽马就下令启锚出航，但偏偏遇上强大的逆风，没办法，葡萄牙人只好硬着头皮在蒙巴萨人的眼皮底下熬了2天2夜，蒙巴萨人也没出来追他们。直到3月14日，风向好转，船队才正式向北航行。
从蒙巴萨北行海里，船队又到了一个海滨小城马林迪。港口里停泊着四艘印度商船，此地离印度不远了，但港口的主人会对他们怎么样呢？幸运得很，马林迪酋长与蒙巴萨首领是死敌，达·伽马是蒙巴萨的敌人，自然就是他的朋友了。在酋长儿子的陪同下，达·伽马一行抵港时受到马林迪乐队和群众的热烈欢迎。身着华丽服装的酋长亲自设宴招待葡萄牙水手，达·伽马与酋长互赠礼品，以示友好。酋长希望达·伽马一行能留下，与他一起对付蒙巴萨人，但达·伽马巧妙地拒绝了，并请求酋长给他们派一名熟悉印度航路的领航员，以便早日完成印度之行。
酋长答应了达·伽马的请求，给他派了一名优秀的领航员——大名鼎鼎的艾赫迈德·伊本·马德内德，他是当时著名的阿拉伯学者和航海家。据说，他编写的航海理论和实践全集至今还保存在法国巴黎的国家图书馆。4月24日，葡萄牙人从马林迪出发直驶印度。
有了伊本·马德内德的领航，又由于马林迪酋长的帮助，新鲜食品和淡水也备足了，特别是想到马上就要到印度了，水手们的情绪特别好。这时西南季风已经吹起，船队借助风力，直穿印度洋，朝东北方向疾驶。伊本·马德内德在达·伽马面前展开了印度洋航海图和印度西海岸地图，向他讲解航行路线和印度西海岸的城市与贸易港口，并指挥船队绕过星罗棋布的岛屿和布满荆棘的暗礁。现在离印度越来越近了，水手们终于有闲心来欣赏一下异国他乡的美丽景色。白天，刺目的阳光照在飞鱼的鳍上反射出耀眼的光芒；入夜，明亮的月光洒在起伏不平的波涛上，如无数的星星在闪烁。慢慢地水手们看到了海鸥在头顶上盘旋，离海岸不远了。5月18日，船员们看到了远处模糊的海岸轮廓，但这时舰队的船只破损厉害，且当地雾气较大，伊本·马德内德建议不在此靠岸。再说，他想把达·伽马一行带到印度西海岸最繁华的港口城市——卡利卡特。于是船队沿印度西海岸南下，岸上的风光像一幅长卷画似的在水手们跟前展开：繁茂的树林遮天蔽日，挺直的椰子树直插云霄；猴子在荡秋千，大象在悠闲地漫步，好和畅的大自然生活。水手们还第一次看到了扁头的鳄鱼，听伊本·马德内德讲述它那可怕的故事。5月20日，伊本·马德内德走到达·伽马面前，指着前方的港口说道：“这就是卡利卡特城，这就是你所向往的国家。”一眼望去，马可·波罗笔下富裕繁华的景象真的出现了。城市展开在宽阔的海岸上，寺院的圆顶高耸在果树和棕榈树林里，清风从岸上送来阵阵花香。经过10个多月的艰难航行，终于到了印度，水手们高兴得跳着、叫着，憧憬着发财的梦。
