僧侣们手持点燃的蜡烛为远航在即的船员们祈祷祝福，码头及道路两房聚集着欢送的人群，其中有即将远航人们的亲人、朋友。从祈祷歌声和小号声中传出了女人恸哭的声音，孩子们也大声哭起来，哭得正像那时一位大诗人写的“比他们知道的还要沉痛”。
国王召见了达·伽马，神父在水边做了弥撒，祈求上帝保佑。船员们登上了船，船锚在辘辘声中升起，篷帆升起了，礼炮轰鸣着，达·伽马率领着船队，一艘接一艘地驶出港口，一次冒险的远航开始了。
史无前例船队驶出港口后，开始朝佛得角群岛全速前进。达·伽马站在旗舰甲板上，望着渐渐远去的家乡，思绪万千。他想起了早晨在伯利恒教堂作完弥撒后，国王曼努埃尔一世亲自授予他一面基督骑士团十字旗；想起了在旗下的宣誓——“为了上帝和国王陛下，不管遇到什么困难，我将高举这面旗帜，勇往直前”；他感到自己责任重大，心里默默地祈求上帝保佑。
出海头几天，风平浪静。好像老天爷要提醒他们远航探险不是件容易的事，船队一过加那利群岛，天气突变，阴霾密布，狂风怒吼，掀起阵阵巨浪，几乎要把整只船吞噬；而浓密的大雾又使水手们看不见前后的船只。船队被风浪打散了，幸亏达·伽马事先有安排，舰队在7月27日于佛得角重新汇合了。
8月3日，舰队驶离佛得角，沿几内亚海岸朝东南方向疾驶。越过圣若瑟要塞，行至北纬10度左右时，船队遇上了强大的逆流和逆风。尽管水手们尽力拼搏，一个个累得精疲力尽，可船队还是无法前进。达·伽马看到蛮干是不行的，当机立断决定改变航行方向，顺风朝西南方驶去，进入茫茫的南大西洋。他的这一举动遭到一些人的不理解和反对，但达·伽马我行我素，毫不动摇。过了赤道后，他才下令转舵朝东南方向航行，而且这时还稍有一点顺风，船队在11月4日到达圣赫勒拿湾。其实，达·伽马这时已无意中发现了从欧洲到非洲南端的最便捷的航线，因为北纬10度附近的风向和水流总是便利帆船向西南方向行驶，越过赤道，再转向东南方，这样又能避免几内亚湾的无风情况，今天的帆船仍然是走的这条路线，可见大胆的冒险精神和坚强的自信心是远航探险成功不可缺少的品格。然而，这样一来，航线拉长了，时间就多了，这段航路走了整整93天。水手们所经受的艰辛是难以名状的，炎热潮湿的天气，受热变质的淡水，一日三餐乏味的咸牛肉，没有新鲜食物的调剂，长期见不到陆地而产生的孤独感，坏血病的侵扰，所有这些几乎使他们无法忍受，不满情绪时有表露。因此，达·伽马宣布在此抛锚，一则让大家休息一下，补充些食物和淡水，二则维修一下船只。
上岸找水的船员，在岸边不远处的一条小河边，发现了两个身材矮小的土着黑人——布须曼人正在采蜂蜜，他们赤身裸体，皮肤就像“干枯的树叶”。水手们抓了一个带到船上，给了他一些食物、几串不值钱的玻璃珠子，然后将其放了。葡萄牙人希望他能带一些人来，果然以后几天天天有一群群的布须曼人来，但他们根本没有带来什么黄金、宝石，也不知道黄金、宝石为何物，这使得水手们大失所望。原来葡萄牙人并不真心想与纯朴的土着交朋友，他们的惟一目的在于利用土着寻找黄金和宝石，既然土着不知黄金为何物，就用不着再与土着保持友好关系了。结果一个傲慢无礼、性格粗鲁的水手与土着发生了争吵，布须曼人用石头和弓箭攻击水手，有几人受伤，达·伽马也被石头砸伤了脚，水手们赶紧开炮把土着人轰走了。为求安全，船队提前驶离此地，向好望角进军。
达·伽马深信好望角就在前方，可究竟在什么地方，心中无数。他决定先朝西南方向行驶一段，越过圣马丁角，两天后，终于从船的左侧看到了陆地，远处出现了海岸的轮廓，船队就朝那边驶去。好望角越来越近，“好望角，风暴角，好望不好过”。狂风呼啸而来，掀起滔天巨浪，以排山倒海之势向船队猛扑过来，船队顿时乱了阵脚。天上的乌云好像就在樯桅顶上飞驰，压得人喘不过气；海上的巨浪一会儿把船抛上云霄，一会儿又像要把它浸入海底，铺天盖地的浪头打在甲板上，似乎要把船击碎，即使经验丰富的老水手也会被它打倒。倾盆大雨也赶来助威，当时南半球正是夏天，可水手们穿着被浪和雨水淋得湿透的衣服，还是感到一阵阵的寒意。真是祸不单行，船底开始漏水了，水手们只好不停地用手摇唧筒向外抽水。达·伽马彻夜不眠，尽管心里也感害怕，但丝毫没有表露出来，指挥若定；而随船的牧师则吓得整天跪在船舱里，喃喃地祈求上帝的保佑。或是水手们的不屈不挠的斗争精神，或是牧师的祈祷感动了上帝，经过3天3夜的狂风恶浪，突然风平浪静。11月22日，达·伽马一行终于穿过好望角，进入西南非洲的极端福尔斯湾。
11月25日，船队驶入莫塞尔湾，也就是当年迪亚士到过的最远处，达·伽马决定在此修理遭暴风雨袭击损坏的船只。当地的土着黑人友好地接待了这些来自远方的异乡人，他们围成一圈，用一些原始的乐器，奏起悠扬的民歌，小伙子、姑娘们踩着歌曲的节奏翩翩起舞。水手们受到感染，也吹起喇叭，唱起那古老的、多少有些伤感的葡萄牙歌谣，表达他们对家乡和亲人的思念。联欢之后，水手们同土着进行了货物交换，他们用几顶红色小帽就换到了土着的一头牛，这些可怜的黑人受到了欺诈还不知道。
过了几天，船员在检修中发现运输船不行了，达·伽马命令将其烧掉，并把货物转移到其他船上。临走之前，葡萄牙人在海岸上竖立了石柱和一个巨大的十字架。
不久，船队就进入欧洲人所不知的海域。虽然海上风光迷人，但这丝毫不能减轻他们想家的苦闷。单调寂寞的生活，对海上漂泊的厌恶，前途未卜的恐惧使水手们牢骚满腹，思乡病再度盛行。恰好这时船队遇到了自北而来的激流的阻挡，无法前进。于是一些水手趁机进行鼓动，北进无望，要求返航；更有甚者，采取行动，拘捕船长，强迫返航。眼看要成为迪亚士第二了，性格果断、手段残忍的达·伽马立即无情地镇压了这次骚动，为了杀一儆百，把为首闹事者扔到大海喂鱼去了。没有剑与火，人类文明的发展是不可能的。
骚动平息了，逆流和无风的天气却无法改变，船队依旧无法北进，而呆在原地又会引起水手们的不安定情绪。达·伽马决定采纳经验丰富的老船员的意见，沿“之”字路线走，终于在1497年圣诞节驶抵今南非的纳塔尔地区。“纳塔尔”一词是葡萄牙语，意即“圣诞节”——据说这名字还是达·伽马所取。1498年1月11日，船队驶到了河口处，并在此停泊休整。水手们受到当地的土着——班图人的友好接待，达·伽马称这地方为“好人国”，并赠短大衣、裤子和帽子给土着酋长，以示友好。
1月16日，船队离开“好人国”继续北上。此时虽有顺风，强大的莫桑比克洋流却顽固地阻挡着舰队的北上，船队仍然只好走“之”字线。这样弯弯曲曲地行驶了近10天，直到1月25日，他们才驶入莫桑比克海岸的克利马港。由于食物中缺少维生素C，这段航程中很多人得了坏血病。当时的一个水手在日记里记道：“现在我们很多人都生起病来了，手脚浮肿，牙床肿胀得张不开嘴，无法进食。”这种情况不但影响到水手们的生命安全，而且更直接影响到达·伽马这次远航印度的成功与否。达·伽马很着急，在船队在此停留的一个多月里，他对伤病员表现出少有的关心，亲自组织与土着的以货易货交易，获得了一些新鲜蔬菜、水果和其他新鲜食物，坏血病得到了有效的治疗。
在此期间，达·伽马还从两位来访的土着首领的衣着和交谈中，敏锐地意识到这里已受到某种高度发达的文明的影响，如果不是印度，就是离此不远的阿拉伯国家了。他的精神为之一振，信心大增，胜利在望。丰富的知识，敏锐的观察和联想，大胆的推理，是达·伽马航海探险成功的又一个重要原因。
1498年2月底，船队重新出航，不久就进入非洲东岸莫桑比克海峡多暗礁险滩的区域，达·伽马一行只好白天行船，晚上停泊，以免黑夜搁浅。3月2日，船队终于驶出莫桑比克海峡，远处的海边有个大港湾，达·伽马决定去那儿暂时歇脚。
海港慢慢地靠近了，一派新的景象渐渐地呈现在眼前，浓绿色的森林无声无息地远去了，隐匿在鲜花盛开、翠绿叶丛之中的白色小屋慢慢地出现了，远处的清真寺也隐约可见。他们来到了深受阿拉伯文化影响的穆斯林城市——莫桑比克。
岸上突然涌出许多阿拉伯人，他们吹着长喇叭，诵着《古兰经》，欢迎达·伽马一伙人的到来。显然，阿拉伯人误把他们当作穆斯林兄弟了，达·伽马将计就计，默默地接受了阿拉伯人的欢迎。
莫桑比克的土着居民主要是黑人，但在13世纪时被阿拉伯人征服。嗣后，阿拉伯人垄断了这里的全部贸易，并带来了伊斯兰文化，当地绝大多数居民皈依了伊斯兰教，成为穆斯林。达·伽马派人拜访了当地酋长，后者祝他们一路顺风。水手们在港内发现了许多来自印度的商船，满载金、银、丁香、珍珠和宝石。葡萄牙人好不嫉妒，当地穆斯林告诉他们，这些东西在印度到处都有，俯拾即是，根本不值钱。此时达·伽马开始意识到今后真正的对手将是阿拉伯人，他们是比暴风浓雾和逆流更危险的敌人。不久，阿拉伯人也发现他们是异教徒，了解到他们去印度的真正目的，就把他们当作敌人看待了。城里居民对他们的态度马上变得冷漠起来，上岸采购货物和装取淡水的水手成为不受欢迎的人，被公开驱赶。达·伽马恼羞成怒，下令炮击岸上的人群，以掩护水手们安全返船。关系彻底恶化，葡萄牙人感到必须离开此地，以防不测。他们抢了附近几条船上的财物，抓了两个莫桑比克的阿拉伯人做领航员，火速起锚出海。阿拉伯人的武装船只追了过来，但毕竟敌不过葡萄牙人猛烈的炮火，先进武器的威力又一次显示出来了。
虽然莫桑比克的追兵被击退了，但洋流和风向却不利于北上，而且在莫桑比克抓到的阿拉伯领航员还有意捣乱，在航途中欺骗水手，谎称群岛为大陆。达·伽马觉得前程更加险恶，命令水手们备加小心，下令严刑拷打了说谎的领航员。为了获得航路的一些确切情况，水手们随后又捕获一艘当地小商船，达·伽马亲自拷问了船主——一个可怜无辜的阿拉伯老头。
船队小心谨慎地前进，现在除了要与恶劣的天气作斗争外，还要对付更可怕的阿拉伯对手。蒙巴萨到了，该城是非洲东岸最大的阿拉伯港口城市，位于岩石遍布的半岛上，这里地形复杂，气候炎热。备尝艰辛的达·伽马由于对阿拉伯人和穆斯林心怀戒备，再加上水手们精疲力竭，不敢贸然入港，就在公海抛锚。据后来获得的情报，这次真够险的了，原来阿拉伯领航员和莫桑比克方面早有密谋，准备在他们进蒙巴萨港时，有意领船触礁。达·伽马的处事沉着冷静又一次挽救了船队的命运。
蒙巴萨的首领已接到莫桑比克人的通知，得知了葡萄牙人的行踪，他认为这伙人不仅是异教徒，而且是自己未来商业上的强大竞争对手，决心趁早除掉他们。首领知道，他无法在公海上打败装备精良、作战经验丰富的葡萄牙舰队，达·伽马的船队不进港，须引诱它进港。首先，首领派人给达·伽马一行送去羊、桔子、柠檬和甘蔗，后又赠予黄金和宝石，并邀请舰队入港。达·伽马表面接受了邀请，但暗底下命令水手们保持警惕，以防意外。
第二天，当舰队准备启程前进时，忽然发生两船相撞事故，接着船上的阿拉伯人纷纷跳入大海，或躲了起来，跳入大海的马上就被附近的阿拉伯船只救走。见此情景，达·伽马什么都明白了，暴跳如雷的他将在莫桑比克抓到的两个领航员严刑拷打，然后下令作好战斗准备。巡逻的水手突然听到船的周围有水响的声音，原来阿拉伯人偷袭来了，一些人正在割缆绳，另一些已经爬上甲板。巡逻者马上发出警报，等到水手们拿着武器出来时，阿拉伯人早已撤退，隐蔽在不远处的小船上。葡萄牙人随时可能遭到蒙巴萨人的进攻，水手们惊恐不安，天一亮，达·伽马就下令启锚出航，但偏偏遇上强大的逆风，没办法，葡萄牙人只好硬着头皮在蒙巴萨人的眼皮底下熬了2天2夜，蒙巴萨人也没出来追他们。直到3月14日，风向好转，船队才正式向北航行。
从蒙巴萨北行海里，船队又到了一个海滨小城马林迪。港口里停泊着四艘印度商船，此地离印度不远了，但港口的主人会对他们怎么样呢？幸运得很，马林迪酋长与蒙巴萨首领是死敌，达·伽马是蒙巴萨的敌人，自然就是他的朋友了。在酋长儿子的陪同下，达·伽马一行抵港时受到马林迪乐队和群众的热烈欢迎。身着华丽服装的酋长亲自设宴招待葡萄牙水手，达·伽马与酋长互赠礼品，以示友好。酋长希望达·伽马一行能留下，与他一起对付蒙巴萨人，但达·伽马巧妙地拒绝了，并请求酋长给他们派一名熟悉印度航路的领航员，以便早日完成印度之行。
酋长答应了达·伽马的请求，给他派了一名优秀的领航员——大名鼎鼎的艾赫迈德·伊本·马德内德，他是当时着名的阿拉伯学者和航海家。据说，他编写的航海理论和实践全集至今还保存在法国巴黎的国家图书馆。4月24日，葡萄牙人从马林迪出发直驶印度。