船队驶出港口后，开始朝佛得角群岛全速前进。达·伽马站在旗舰甲板上，望着渐渐远去的家乡，思绪万千。他想起了早晨在伯利恒教堂作完弥撒后，国王曼努埃尔一世亲自授予他一面基督骑士团十字旗；想起了在旗下的宣誓——“为了上帝和国王陛下，不管遇到什么困难，我将高举这面旗帜，勇往直前”；他感到自己责任重大，心里默默地祈求上帝保佑。
出海头几天，风平浪静。好像老天爷要提醒他们远航探险不是件容易的事，船队一过加那利群岛，天气突变，阴霾密布，狂风怒吼，掀起阵阵巨浪，几乎要把整只船吞噬；而浓密的大雾又使水手们看不见前后的船只。船队被风浪打散了，幸亏达·伽马事先有安排，舰队在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，这段航程中很多人得了坏血病。当时的一个水手在日记里记道：“现在我们很多人都生起病来了，手脚浮肿，牙床肿胀得张不开嘴，无法进食。”这种情况不但影响到水手们的生命安全，而且更直接影响到达·伽马这次远航印度的成功与否。达·伽马很着急，在船队在此停留的一个多月里，他对伤病员表现出少有的关心，亲自组织与土著的以货易货交易，获得了一些新鲜蔬菜、水果和其他新鲜食物，坏血病得到了有效的治疗。