神情堅定的土耳其人要屈膝懇求，
此刻的印度君主，安全又自由，
但在你強有力的君主的束縛之下也要彎腰，
因為你的公正法令遍及整個東方。
——卡蒙伊斯《盧濟塔尼亞人之歌》，第二卷（由米克爾所譯，1778年）
1498年4月，瓦斯科·達·伽馬的小船隊沿著東非海岸繼續向北，朝著赤道航行，這距離他們在大西洋向南航行已經過去了漫長的9個月。每向前一里格，孤獨感就增加一分，距離他們的祖國葡萄牙和熟悉的海域就更遠一分。儘管在蒙巴薩的停留使一些生病的船員恢復了健康，但是出發時的180多名船員，一直因為壞血病、逃亡，以及與敵對的穆斯林的小規模作戰而不斷減少。宗教隔離感對於這些強烈依靠對救世主信仰的人而言是最艱難的，因為無論肉體上的痛苦如何，他們對基督教的信仰都堅定不移。
與祭司王約翰聯手，從「航海者亨利」的時代起就是鼓舞他們遠洋探險的動力，而自從他們繞過好望角之後，距離這個目標的實現似乎就更近了：每次一有機會他們就派遣間諜登岸，搜尋那位神聖又好戰的統治者的訊息，但是結果總是徒勞。對祭司王約翰的探尋，可能一度幫助達·伽馬維持了船員的鬥志，並且使他們相信，繞過下一個海岬就會有一個友善的基督徒港口歡迎他們。但是在他們繞過好望角，向北航行了將近3000英里之後，這些希望逐漸消退了，因為他們看到在斯瓦希里海岸阿拉伯人的影響在持續增強。這些人知道，他們正在向伊斯蘭世界的中心地帶航行。
達·伽馬和他的船員們對信仰的依賴，以及他們對所有穆斯林縈繞於心的仇恨，與幾個世紀以來，在伊比利亞半島和摩洛哥發生的宗教衝突的背景有關。聖戰是他們在精神上所接受的宗教佈道的永恆主題，他們從佈道中獲得的資訊是基督教的優越性不容置疑。而且，他們進入印度洋的時間，正是歐洲和近東這兩大宗教力量的相互競爭達到頂點的時期。和哥倫布一樣，達·伽馬也相信全世界都皈依基督教是《聖經》安排好了的，他們的遠航就是為了幫助上帝實現這個目標。同樣，奧斯曼土耳其人相信安拉選擇他們在全世界傳播伊斯蘭教，佔領君士坦丁堡只是實現這個目標的其中一個步驟。
葡萄牙的天主教徒和奧斯曼土耳其人將他們自己內部的持異議者視作異教徒，認為他們應該被殘酷地對待；但是土耳其人受《古蘭經》的影響，認為他們的基督徒敵人是信徒、「聖書的子民」，而葡萄牙的天主教徒對穆斯林和其他人做了更精確的區分，認為前者是在魔鬼掌控下的受到詛咒的靈魂，後者則是無信仰者，前者必須被摧毀以取悅上帝，而後者只需要等待他們皈依真正的信仰。這種前提支配篤信基督教的葡萄牙人如何對待剛果人和異教徒，就像影響他們之後如何對待印度人一樣。
然而，一定有偏見屈服於眼前需求的時候，從蒙巴薩逃離後，在船隊於馬林迪港停留時就出現了這種情況。葡萄牙人發現，這兩個斯瓦希里城市——蒙巴薩和馬林迪——相互敵對，於是為了自己的利益，他們打算利用這一點。毫無疑問，馬林迪是穆斯林的地盤，但是沿著東非海岸交朋友的願望，使得遠道而來的葡萄牙人對這一點視若無睹。「聖加百列」號上有一個來自馬林迪的人質，他好像「有點兒身份」，當葡萄牙人抓捕並且搶掠一艘經過的單桅帆船時，這個人跳到海里想要逃跑，但是被船上的鉤竿撈了上來。這個人慫恿達·伽馬駛往他的母港，說在那裡很容易找到熟悉去印度線路的領航員。
猶豫再三，馬林迪的蘇丹和當地貴族足夠精明，表現出對這些稀奇的陌生人的歡迎姿態。考慮到已經很快在海岸地帶傳開的、關於葡萄牙人好戰且作戰勇猛的訊息，馬林迪人採取的態度也有自保的動機。除了這個因素之外，蘇丹總想尋找新的盟友一起對付蒙巴薩。儘管馬林迪分佈有十幾座清真寺，但是長久以來它都是一座世界化的城市，它與印度、孟加拉和波斯聯絡密切（與波斯人一樣，馬林迪人也是什葉派穆斯林）。80年前使中國人驚訝不已的長頸鹿就來自這裡。
達·伽馬立刻意識到，馬林迪港無法和蒙巴薩港相比，但是它足夠安全，可以為船隻提供庇護，躲避壞天氣。海岸的景色讓人印象深刻：「這座城市坐落在一片寬闊的海濱地帶，周邊環繞著許多棕櫚樹和其他種類的樹木，它們整年都是綠油油的，這裡還有許多花園和果園。」為了使馬林迪人相信他們的善意，葡萄牙人釋放了他們的俘虜，將他放在海岸邊的沙洲上。他被告知要向他的同胞們保證，這些陌生人平和安靜，他們花了兩年的時間才抵達東非（這兩點都被誇大了）。之後，達·伽馬向岸上傳遞訊息，強調他的國王是「世界上最偉大的基督徒統治者」，並且說到達馬林迪的這三條船是一支由一百艘船組成的艦隊的一部分，這支艦隊正從事一次偉大的航海探險。
這番說辭給蘇丹留下了深刻印象，他的第一個舉措是派遣一隻載著羊、桔子和甘蔗的船去慰問他們。達·伽馬派了一個罪犯帶著一件黃色短外套、一頂帽子、一些項鍊、黃銅杯子和各種小裝飾品上岸。這個試探的過程持續了幾天，直到蘇丹乘坐一艘裝飾著掛毯的禮儀船出海，這艘船停靠在「聖加百列」號旁邊。達·伽馬穿著他華麗的深紅色斗篷歡迎他，帶他參觀整條船，他們還鳴響加農炮以示敬意。蘇丹穿著顏色明亮的絲綢衣服，他的銀鞘寶劍放在一個古老的架子上，巨大的紅色遮陽傘高舉在他的頭頂上方，他的寶座上裝飾著銅製品，而他的樂隊正在奏響喇叭和象牙號角，對於這一切，葡萄牙人豔羨不已。由於害怕對方耍花招，達·伽馬拒絕了上岸的邀請，只允許他的幾個人拜訪蘇丹的宮殿，並交出人質作為他們安全返回的保證。維利烏在日記中感慨地寫道，馬林迪使他想起塔霍河畔的小鎮阿克契特。
斯瓦希里海岸流傳一種說法：「蒙巴薩有騎馬的戰士，而馬林迪的女人妙不可言。」這是說一個城市誇口有更好的戰士，另一個城市則有更漂亮的女人。葡萄牙人在馬林迪停留了9天，期間沒有足夠的機會了解馬林迪的女人，但是他們至少能夠欣賞這座城市生活的文明程度。根據一個編年史家的記載，那裡的花園有「各種藥草和水果」，特別是那裡的大桔子「清甜可口」。用石灰和石頭建成的房子沿著整齊的街道排列。
馬林迪的大多數居民是黑人，他們之中也有來自阿拉伯和印度的商人。由於印度是葡萄牙人的目的地，他們努力說服自己印度的大多數人是基督徒，他們還研究鄰近船隻的水手：「這些印度人的皮膚是黃褐色的。他們穿得很少，留著長鬍子和編成辮子的長頭髮。他們告訴我們，他們不吃牛肉。他們的語言不同於阿拉伯人所講的語言，但是他們中的一些人懂一點阿拉伯語。」
在節日期間，當地人和他們的客人都參與進來，年邁、半盲的前任蘇丹被人用小轎子抬到海邊來。當地的青年騎著馬，沿著海灘飛快地賓士。夜幕降臨，葡萄牙人和印度人的船向天空發射煙火。
儘管這裡的競爭都是出於好意，但達·伽馬還是渴望抓住機會離開。雖然他曾向他的國王發誓他會抵達卡利卡特，但是他的船員們思念家鄉，而且瞭解到去往印度還需航行幾個星期。因此，當招募到一個自願為他們領航又有穿越印度洋經驗的人時，他大大地鬆了一口氣。因為之前他曾努力勸說過的所有斯瓦希里水手，都直接拒絕給他的小船隊當領航員，要麼是出於害怕要麼是出於蔑視，「即便讓他們受盡折磨」也不起作用。
在馬林迪，他們的命運發生了轉變。蘇丹提供給他們一位阿拉伯遠航船長，維利烏將他的名字寫為馬萊馬·卡納或者卡納誇。這位年長的「古吉拉特摩爾人」對於前往卡利卡特的路線很熟悉，他願意為這批基督徒新來者擔當嚮導。他展現了在海上找到方位的航海技能，他有一張印度西側海域的航海圖，並且在看到葡萄牙人向他展示的星盤時毫不驚訝。
在離開馬林迪之前，達·伽馬又派了一個罪犯上岸，給了他一些錢，還給了他一張授權書，說明他代表的是葡萄牙。我們不知道這個人的姓名，他可能受過一些教育，可以被視為東非最早的歐洲定居者。他被告知要盡一切可能探索這片大陸（毫無疑問，當然是打聽祭司王約翰的訊息）。達·伽馬向他承諾，只要他能活著回到里斯本，他就能恢復名譽，成為「一名皇家紳士」。關於他之後的命運，沒有相關記錄。
蘇丹和葡萄牙人告別。葡萄牙人的領航員指揮船隊向東北方向進發，始終在能見到海岸的範圍內航行。很快，大陸開始改變，蒼翠的棕櫚樹林和紅樹林變成了乾燥荒蕪的沙灘。但是達·伽馬的船員們從天象判斷出他們又回到了北半球，為此他們歡喜不已：「下個禮拜日，我們的人看到了北半球，他們也能看到南半球，他們感謝上帝賜予的好運。」5天后，船隊抵達一片長長的沙灘，領航員稱之為賽義夫·塔維勒（saifal-tawil），就是在那裡，他轉換方向，遠離非洲，朝著幾乎正東的方向前進。葡萄牙水手對他使用的航海儀器以及他全身透出的愉悅和自信印象深刻。他們知道，他們的命運就掌握在他的手中。
又航行了23天，這些天恰好都是晴好天氣，瞭望員喊了起來，因為印度海岸出現在他的視野中。在經歷了史上最漫長的航程之後，達·伽馬終於完成了他的使命。那一天是1498年5月18日。他必須準備好去覲見他所知曉的印度海岸最強有力的統治者，也就是國王曼努埃爾在給他的信中所說的「卡利卡特的王侯」。對達·伽馬來說，乘著3艘飽經風雨的小船，還要表現得體面而有尊嚴，不是一件容易的事。開啟防水的箱子之後，達·伽馬也必然意識到，他們給王侯的禮物似乎顯得既廉價又俗麗。但是他仍保有雙重信念——上帝和槍炮。
領航員在離卡利卡特北部很近的地方登陸。此處水深45英尋。之後，他們向南航行，經歷雷電交加的暴風雨。當他們在卡利卡特拋錨的時候，他們眼前的景象與佩羅·德·科維良和尼科洛·德·孔蒂的記述一模一樣：一個開放的港口，裡邊有各式船隻，海岸上分佈著商店和貨棧，一個巨大的城市坐落其後。海港的側方有一些入口，船隻可以在裡邊躲避大的風浪。
葡萄牙人的船隻不同於之前在印度見過的任何船隻，因此他們的到來引起了當地人的興趣。小船裡坐滿了瞧熱鬧的人，他們帶著自己的孩子，「興高采烈地去看葡萄牙人的船」。其他小船「用魚、椰子和家禽換取葡萄牙人的餅乾和錢」。儘管達·伽馬一行人的這次遠航是距離他們家鄉最遠的一次，但他們的精神很振奮：「在葡萄牙他們幾乎沒想過，他們能在這裡受到如此熱烈的歡迎。」
和以往一樣，第一個被派上岸的人還是罪犯之中的一個。他名叫若昂·努涅斯，是一個能講希伯來語、阿拉伯語、葡萄牙語和西班牙語的「新基督徒」，是「一個有敏銳理解力的人」。當他正準備呈遞國王曼努埃爾的信時，他震驚地聽到一個旁觀者用西班牙語對他說：「願魔鬼將你帶走！是什麼帶你來到這裡？」
這個人的身份在關於這個事件的多個版本的記錄中有不同說法。根據其中一份記述，他是塞維利亞人，名叫阿隆索·佩雷斯，他在西班牙作戰期間被阿拉伯人俘虜，之後以俘虜的身份被帶到各種地方，在皈依伊斯蘭教之後被釋放。而根據另一個版本的記錄，向努涅斯粗魯地打招呼的人是一名突尼西亞商人，他叫作邦泰博。之後，他把努涅斯帶到自己家裡，用麵包和蜂蜜款待了他。無論哪一種說法是真的，它們都表明在伊斯蘭世界內部旅行的自由度非常高。努涅斯回報達·伽馬，當被問及為什麼葡萄牙人來到印度的問題時，他的回答是：「我們是來尋找基督徒和香料的。」作為一個被迫改信基督教的猶太教徒，如果努涅斯的回答讓狂熱的基督教徒達·伽馬不滿意，他會因為冒犯被判有罪而被吊死，所以努涅斯回答時聰明地將基督徒放在了香料的前面。
葡萄牙人被卡利卡特的富饒深深吸引。那裡有一條人潮擁擠的林蔭大道，直通王宮。地面上落滿了從道旁的樹上掉落的白色花朵。宮殿佔地1平方英里，四周環繞有刷了明亮顏色的高牆。大人物們在城中行動時乘坐轎子，轎子前面會有吹喇叭的人清道開路。轎子里人的身份地位不同，轎子前面的人吹的喇叭也有區別，有的是黃金的，有的則是黃銅的。