歐洲的船長、船員和探險家們最重要的不同在於，他們擁有可以實現其野心的船隻和槍炮，並且他們來自一個熱衷競爭、冒險和創業的政治環境。
——保羅·肯尼迪《大國的興衰》，1988年
當巴爾託洛梅烏·迪亞士繞過好望角的時候，他的國家作為一個世界強國登上歷史舞臺的時機已經到來。奇怪的是，葡萄牙在邁出最後一步之前，似乎在這個最佳時機面前猶豫了幾乎10年。迪亞士證明了科維良的報告內容：從非洲南部到印度，「全程都是海」。前往東方的航路是公開的，但是在1490—1495年這個重要時期，也就是哥倫布兩次航行穿越大西洋的時期，葡萄牙人似乎什麼都沒做。真相卻是他們暗中做了很多事。
就如同在哥倫布之前可能有其他歐洲人抵達過美洲一樣，幾乎沒有什麼疑問的是在1488年迪亞士返回里斯本和瓦斯科·達·伽馬在1497年開始其歷史性的航行之間，葡萄牙人已經成功進入印度洋，只不過這些航行未被記錄下來。線索就在葡萄牙的檔案裡，那裡還保留有給船隻供應餅乾的皇家訂單，這些被戲稱為「硬麵包」的餅乾被分發給輕快帆船的船員們。1488年之後，這些餅乾能夠支援80次航行，但是目的地通常不公開。因此在1489年8月，即迪亞士回來9個月之後，從王室國庫發出兩批連續的訂單，一個是40噸，另一個是60噸，每一批餅乾都能夠支援兩艘輕快帆船進行長達18個月甚至更長時間的航行（迪亞士的航行所花的時間就是那麼長）。而60噸的餅乾訂單關於它們應該交付給誰的說明還很神秘，「國王會有所指示」。
只有在這些秘密的航行中獲得的經驗，才能解釋瓦斯科·達·伽馬的船隻向西南航行穿過大西洋，遠離陸地3個月，然後又藉著信風向東南方向航行，最後在好望角以北大概100英里處準確登陸（他們使用了扎庫託教授在《天文法則》中的表格）。這次航行中間沒有停頓，航程長達4500英里，在歐洲的航海技術史上沒有能與之比肩的航行。這條航線完全不同於10年前巴爾託洛梅烏·迪亞士選擇的路線，後者的輕快帆船緊鄰非洲海岸航行，在向南航行的過程中痛苦地遭受逆風的襲擊。
據說瓦斯科·達·伽馬被選為這次歷史性遠航的指揮，是因為他「對於航海之事富有經驗」，但是除了有記載說明1492年他經過短暫航行在葡萄牙的海域抓獲了幾艘法國船隻之外，不存在任何能夠說明他的航海經驗的記錄。而且巧合的是，葡萄牙的皇家檔案館丟失了1493—1495年的所有記錄。因此，我的猜測是瓦斯科·達·伽馬必定是在迪亞士抵達好望角之後葡萄牙似乎處於休止狀態的10年裡，指揮過某次未被記錄的遠航，從而瞭解了那些「航海之事」。
1500年，在印度洋那一側一位名叫伊本·馬吉德的阿拉伯船長寫了一首散文詩，講述了這個故事，詩的題目是「索法拉之路」，在某種程度上它算是前往東非海岸的指導說明，但它還描述了葡萄牙人的到訪情況。伊本·馬吉德在一處這樣寫道：
就是在這裡（索法拉附近）葡萄牙人被困住了，因為他們相信在聖米迦勒節這天會有季風，但似乎……海浪當頭，將他們拋向索法拉礁石的對面。桅杆淹沒在水中，船裡滿是海水。一些人眼看要淹死……900年，葡萄牙人的船隻航向更北的地方。他們航行了整整兩年，一直想要到達印度。
伊斯蘭曆的900年轉化成基督紀元就變成了1495—1496年，比瓦斯科·達·伽馬在眾人的歡呼聲中開始遠航早了兩年，而9月29日那一天是聖米迦勒節（雖然伊本·馬吉德知道這個節日，但這是一個純粹的基督教節日），那正是季風改變風向的時候。
因此，伊本·馬吉德的散文詩暗示，不熟悉印度洋風向模式的葡萄牙人，在探索前往東方的海路時，也遭受了損失。葡萄牙從未揭示真實情況，但是伊本·馬吉德一定知道，因為他後來與葡萄牙人交往密切。
葡萄牙人遲遲沒有將這樣一個具有重要意義的遠航付諸行動，還有其他理由，這些遠航被認為要麼獲利頗豐要麼損失慘重。其中一個理由是葡萄牙在哥倫布於1493年從加勒比海地區返回之後，與西班牙「分割世界」的需要。只有在這件事達成之後，葡萄牙人才感覺自己受到保護，不至於被比自己強大的鄰居在背後捅一刀。為了達成這個協議，在1493年4月，也就是在哥倫布返航後一個月，若昂二世威脅說要派遣一支無敵艦隊，以宣稱對亞速爾群島以西所有土地的主權，因為西班牙「侵犯了葡萄牙的權利」。他的恐嚇起到了作用：西班牙的斐迪南和伊莎貝拉屈尊達成了協議。從西班牙的穆斯林手中奪取了格拉納達，以及哥倫布的勝利返航，使得他們此時能夠表現得格外慷慨。
《托爾德西里亞斯條約》（在1494年6月簽署）包含了教皇裁定的結果。雙方同意在維德角群島以西370裡格處劃界，史稱「教皇子午線」。該線以西的一切土地——哥倫布新發現的地方——都劃歸西班牙；該線以東的整個世界都劃歸葡萄牙，包括非洲和整個印度洋。
葡萄牙王室下達了建造幾艘精良船隻的命令。它們必須被設計成能夠承擔比歐洲有史以來任何一次航行的距離都更遠的航行。製作船隻外殼的橡木經過精挑細選和切割，然後被運到里斯本，在那裡繞過好望角的船長巴爾託洛梅烏·迪亞士全權負責所有的準備工作。他十分看重這項任務，設計了兩艘比輕快帆船大的堅固的方帆船。
這些船隻對於船員來講更加舒適，如果到了印度，它們的運載量更大，能夠運回更多的香料和其他的東方奢侈品。葡萄牙裝備這些船隻不計成本。迪亞士堅持要求，這兩艘船的所有部件都可以相互替換，並且每艘船都有兩套完整的帆纜。旗艦應該是一個移動的堡壘，裝有20門加農炮，足夠堅固，可以應對從側翼開炮的衝擊力。每艘船還要配有火繩槍和小型的手持炮，以便在近距離交火時能夠有效應對。
若昂二世對他的國家滿懷雄心，但是他沒能看到這些船隻起航。1494年底，他浮腫得厲害，9個月過後就去世了。由於他的兒子阿方索，即他的繼承人，之前從馬上不慎跌落，傷重去世了，按照繼承順序，若昂的王位由他的妹夫——無能且嫉妒心強烈的曼努埃爾——繼承。他是7年前給科維良和派瓦秘密傳達簡短指令的小組成員之一。
曼努埃爾對征服印度洋有強烈的慾望，但是在此之前需要解決更為急迫的事情。這些事情涉及葡萄牙的猶太人和穆斯林。3年前斐迪南和伊莎貝拉已經樹立了一個先例：所有的非基督教徒都被趕出西班牙的國土，甚至那些祖輩已經在這個國家生活了幾個世紀的人也不例外。成千上萬的猶太人和穆斯林逃往土耳其人控制的安全地帶。至少有10萬猶太人——相當於當時西班牙總人口的十分之一——逃往葡萄牙。新國王曼努埃爾娶了可憐的阿方索王子的年輕遺孀。她是強大的西班牙統治者的女兒，而他們能夠締結婚姻的主要條件就是葡萄牙之後必須採取和西班牙一樣的宗教法令。
因而，1496年葡萄牙頒佈了這樣的法令：每一個「不接受基督教洗禮的」猶太人和穆斯林都必須在10個月以內離開葡萄牙。此法令對來自西班牙的難民和世代居住在葡萄牙的非基督徒都有效：醫生、商人和工匠，無論從事何種職業都受到波及。所有14歲以下的猶太和穆斯林兒童都被迫接受洗禮，許多孩子尖叫著被拖進教堂接受洗禮。如果逃往其他國家，就要面對再也見不到自己孩子的命運，因而數以萬計的成年猶太人被迫選擇接受洗禮。他們成為所謂的「新基督徒」，還取了葡文名字。但是他們並沒有因此而獲得認可：他們被嘲笑為「從牙縫裡剔出去的基督徒」（christiansfromtheteethout）。
除了以上人群所遭受的苦難，這些事件在里斯本還引發了商業動亂。然而，這也立刻就給曼努埃爾帶來了好處（他的綽號就是「幸運兒」），因為被驅逐出去的猶太人和穆斯林的生意被基督騎士團沒收了，而從亨利王子的時代起基督騎士團就成為王室的傀儡。這些舉措的諷刺之處在於，非基督徒學者在幫助葡萄牙水手尋找前往東方的海路的過程中出了很大的力。但是大部分被查封的生意都出租給了來自佛羅倫薩的義大利人，因為他們在王室財政空虛時及時提供了資金。曼努埃爾需要錢，特別是供給瓦斯科·達·伽馬即將率領的遠航的資金。
在曼努埃爾滿意地解決了猶太人的問題之後，瓦斯科·達·伽馬也準備就緒。他共有148名船員，他們都經過了嚴格的挑選，報酬要比普通葡萄牙船隻上的船員高得多。一位受人尊敬的船長杜阿爾特·帕切科·佩雷拉，在幾年後不無嫉妒地寫道：「花在這次遠航的幾艘船上的費用太大了，以至我不想多說細節，因為沒人會信以為真。」一份記錄顯示，作為船隊領隊的瓦斯科·達·伽馬在遠航之前被給予2000金克魯扎多，在那時這是一大筆錢。他的哥哥保羅任副領隊，也被給予一筆相同數額的財富。所有船員都預先領到了一筆錢，以便在他們出海期間能夠維繫其家庭開銷。每件事都被詳細規劃。船隻所帶的食物能夠維持3年，分配給每個人的日常給養十分充裕：1.5磅餅乾，1磅牛肉或者0.5磅豬肉，2.5品脫淡水，1.5品脫酒、油和醋。其他供應品包括麵粉、沙丁魚、幹李子、杏仁、大蒜、鹽、芥末、糖和蜂蜜。
1497年初，一切準備停當。剩下來要做的就是等待年中最佳風向的到來。他們的旗艦「聖加百列」號，載重不到300噸，而隨同它一起遠航的「聖拉斐爾」號甚至更小。儘管如此，當風鼓起它們白色的、上面飾以基督騎士團的血紅十字架的船帆時，場面仍頗令人自豪。旗艦的名字反映出瓦斯科·達·伽馬對他所負使命的信仰，因為大天使加百列是天堂的信使，是神聖真理的象徵。船隊中的其他兩艘船是普通的輕快帆船，一艘是「貝里奧」號，另一艘是沒有配備武器的供給船，只要兩艘主艦將供應品消耗到能夠將供給船上的貨物轉移到它們船艙的程度，這艘供給船就會被拆解。
180多名候補船員大多數是精挑細選出來的、具有航海經驗的水手和能夠應對陸上或者海上任務計程車兵。還有工匠，特別是木匠和槍匠。此外，還有西非黑人奴隸，因為在遙遠的大陸另一側，他們可能更容易贏得當地人的友誼。所有船員中最重要的是領航員和航海家，他們曾沿著非洲的海岸南下航行，其中包括一個名叫佩羅·德·阿倫克爾的人，他曾隨迪亞士航行去過好望角。12個罪犯最有可能被捨棄，他們可能被派到未知的地方登岸，以便發現當地居民對他們會持何種歡迎態度。他們中的大部分人是自願參與這次遠航的，以逃避本該執行的處決。還有幾個人被選中，因為他們精通阿拉伯語，據瞭解，阿拉伯語是當時已知的環印度洋地區最常用的一種語言。
在船隊出發前夜，瓦斯科·達·伽馬及其船隊中的高階海員在亨利王子主持建造的一座小教堂裡祈禱。他們將自己看作救世主，併為此迷醉不已，他們發誓不成功便成仁：如果船隊不能帶著國王曼努埃爾的旗幟和基督騎士團的十字架徽紋穿越東方的海域，他們就絕不返回葡萄牙。第二天一早，達·伽馬引領莊嚴的隊伍穿過里斯本的街道，前往港口。他和他的船員們赤著腳，只穿著樸素的及膝束腰寬鬆外衣。他們持著蠟燭，跪下來接受對他們所有罪行的寬恕，然後閱讀教皇給這些前往未知目的地的遠航者的敕令。鼓聲陣陣，教士唱誦，觀者流淚。瓦斯科·達·伽馬被宗教情感所懾：他臉色蠟黃、滿面鬍鬚，眼睛卻熠熠生輝。他的胸前掛著一個鍍金十字架，從他的紅色頸巾裡墜下來，因為他所要從事的遠洋探索也是一場神聖的十字軍東征。
一些小船載著船員的親戚，隨同遠航船隻航行了一會兒，他們不停揮手和喊叫，向這些船員做最後的送別。與這些小船分別之後，遠航船隻向著塔霍河的河口進發，但是此時的風向並不合適，因此瓦斯科·達·伽馬不得不讓他的船隊停泊3天。1497年7月8日，風向發生了改變，遠航船隊啟程前往他們的第一站維德角群島，船員們完全相信上帝會給予他們比4年前熱那亞的哥倫布更豐厚的獎賞。
「以上帝之名。阿門！」這是達·伽馬船上一個名叫阿爾瓦羅·維利烏計程車兵日記開頭的幾個詞。他是這次遠航的見證者，儘管有時候比較乏味，但是他的記錄（沒有其他記錄留下來）表達清楚、文筆流暢。從維德角群島進入南大西洋的航行長達90天，在這整整3個月中不見陸地（對比來看，1492年哥倫布的發現之旅只有33天不見陸地），他對此不以為意，令人驚訝，這一點強烈地表明，維利烏的同行者中有人之前走過這條使人畏縮的路線。
在航行了4000英里之後，11月4日他們在好望角附近望見了非洲的海岸線。為了慶祝這個航海壯舉，他們穿上了「節日服裝」，並且用旗子裝飾船隻。之後，他們花費了一週的時間，清理狹窄、髒臭的船隻。他們遇到了當地的居民：他們抓獲了一個小孩子，把他交給了被稱作「船上的小夥子們」的黑人奴隸，並且要求他們好好對待這個孩子。當地人對這些陌生人並不順從，在一次衝突中，達·伽馬被長矛刺中，受了輕傷。
11月27日，他們再次啟程，繞過了令人畏懼的好望角。之後的幾個星期，他們忙於應對暴風雨和強烈的洋流。他們開始補充淡水，併到達納塔爾海岸（之所以命名為「納塔爾」，是因為這時候快到聖誕節了）附近。這期間發生了一個和9年前擊敗迪亞士的陰謀類似的事件，幾個船員想返回葡萄牙，而非繼續與未知的危險相抗衡。達·伽馬採取的手段是監禁為首的反叛船員。