當總督再次出現在馬薩瓦時，他沒有被這個訊息嚇倒，他決定派遣400名志願者前往衣索比亞高原，因為遠征隊的任何一名成員似乎都難逃一死，而克里斯托弗「也願意為國王做出犧牲，因而不是由其他兒子」，而是由他率領這些志願者。他們不缺願意同克里斯托弗一起遠征的志願者，因為25歲的克里斯托弗精力充沛且以勇敢著稱。他們對以基督教之名殉道的前景熱切不已，於1541年7月9日向內陸進發。他們用騾子馱載10門大炮、迴旋槍、1000把火槍和大量彈藥。與這些志願者一同前往的，還有鐵匠、木匠、軍械士、鞋匠、號手和鼓手。還有150個奴隸。
這場旅途十分艱難。在炎熱的沿海平原上，只有晚上才能行軍。在上高地時，克里斯托弗和他的軍官們幫著拖拽大炮，使它們爬上陡峭的坡地。戰爭毀壞了鄉村，農田荒蕪、食物短缺，只有大量的野生動物。18歲的克勞迪烏斯率領剩餘的衣索比亞軍隊，他們距離南邊的紹阿還有幾百英里。但此時正值雨季高峰期，所以葡萄牙人根本無法在幾個月內和他們會合。
葡萄牙人利用這次延誤從高原北部邊緣的安巴山釋放了勒布納·登格爾的寡婦。這座山的山頂多年來是囚禁王后薩布拉-旺格爾和她的一個兒子的監獄（她被關在那裡，一定程度上使她得以擺脫落入已經圍攻這座山一年之久的格蘭手中的命運，但是另一方面也使她和她的兒子遠離衣索比亞的權力中心）。這座山的兩側非常陡峭，按照一位葡萄牙人的記述，「它們就像是被斧鎬砍出來的」，以至於克里斯托弗派遣的兩個先行軍官在巖面的最後一段距離時，不得不坐在籃子裡被逐個拉上來。
王后從山上下來、問候她的解救者的場景，被達·伽馬的一位船長米格爾·德·卡斯塔尼奧索描述得十分浪漫：
他和他的軍隊莊嚴地迎接她，他之前下令所有人都要穿戴整齊、排好佇列，船長和他們計程車兵、所有的火槍手，打著上面有紅色十字的藍白相間錦緞旗幟，其餘軍隊前方則打著有基督十字的深紅色和白色相間的錦緞皇家旗幟。指揮官是一個身量高大的紳士，穿著緊身褲、飾有許多用金線錦緞編成的辮狀條帶的紅緞馬甲，披著一件縫有金線的法式黑色斗篷，頭戴一頂配有昂貴飾物的黑色帽子。
不久，他們繼續前進，去與格蘭和他的土耳其僱傭軍作戰。騾子馱著物資，用公牛拖拽的雪橇載著大炮。達·伽馬和他的人一起步行。1542年2月初，第一場小規模戰鬥打響了，葡萄牙人擊退了一支想要阻攔他們的穆斯林軍隊。這一役他們佔領了一座清真寺，克里斯托弗下令將它變為一座教堂，還將它命名為「我們的勝利女神」。之後，葡萄牙人轟炸並且猛攻一座由1500名弓箭手戍守的山上要塞，所有的俘虜都被200名與這些白人新來者共命運的衣索比亞長矛兵屠殺。
當葡萄牙人靠近衣索比亞中心時，他們遭遇來自青尼羅河的發源地塔納湖、由格蘭率領的穆斯林主力部隊。信使在兩軍之間來來回回，傳遞譏刺之言或者威脅之論。格蘭說他聽說基督徒的指揮官「還是個沒有經驗的……天真少年」，所以出於同情他會讓他毫髮無損地離開這個國家。克里斯托弗則讓人送給對方一面大鏡子和一副拔眉毛的鑷子，這暗示他的敵人只適合做一些女人似的消遣。
在非洲東側的幾場陸地戰之後，穆斯林和歐洲基督徒又進行了數場遭遇戰。起初，葡萄牙人佔據優勢：不但格蘭受傷，被迫撤退，而且他的軍隊無奈放棄大量的食物補給，而這正是葡萄牙軍隊急需的。穆斯林婦女也被丟在後邊：「在留下來的許多貴族婦女之中，有一位埃米爾的妻子非常美麗，克里斯托弗把她留給了自己。」
這支人數不多的葡萄牙軍隊有很多軍火。而且，他們教衣索比亞人如何製造和使用這些火藥。這迫使格蘭向東邊的紅海方向撤退，但是他很快就獲得了來自阿拉伯半島將近1000名火槍手和10門大炮的增援。穆斯林很快就對法蘭克人實施報復，他們在雨季行軍，想要趁敵不備發起攻擊。在最後的戰鬥中，葡萄牙人的數量完全不敵對方，穆斯林取得大勝，幾乎半數的葡萄牙人被殺死，其餘人連夜逃跑。重傷的克里斯托弗·達·伽馬伏在一頭騾子身上勉強逃離（這頭騾子之後被殺死，以便用它的油脂包紮傷口）。
穆斯林很快對包括克里斯托弗在內的受傷逃亡者形成合圍之勢，並且在他們的領袖面前列隊炫耀。格蘭滿足地坐在這場戰鬥中被割下的160個葡萄牙人的頭顱之間。在被斬首和分屍之前，克里斯托弗·達·伽馬被剝掉衣服，遭受鞭笞，接著他們用在第一次交戰之前他為了諷刺埃米爾派人送去的鑷子，拔下了他的眉毛和睫毛。這距離他和他的哥哥在馬薩瓦分別時他哥哥承諾他的殉難只過了一年多時間。
倖存下來的葡萄牙人和衣索比亞的主力部隊一起組建軍隊，想幫助他們扭轉戰局。格蘭在新獲得的勝利之後非常自信，以至他將土耳其火槍手送回了他們的故鄉，但不到兩個月，他就在克勞迪烏斯發起的一次突襲中被抓，並且被達·伽馬之前的男僕開槍打死。穆斯林軍紀隨之崩潰，士兵們毫無秩序地逃向海岸。在15年的毀滅性戰爭之後，衣索比亞終於再次迎來和平，克勞迪烏斯開始努力使這個國家恢復勒布納·登格爾統治早期的繁榮。
克里斯托弗·達·伽馬的勝利和死亡的訊息最早是由米格爾·德·卡斯塔尼奧索傳到外界的，他帶著其餘50名倖存者奮力趕往馬薩瓦，希望能在那裡找到葡萄牙船隻。（國王阻止遠征隊的其他船隻到達海岸。）他們在那裡的確等到了一艘船，但是它既小又擁擠，只能再擠下一個人。卡斯塔尼奧索是船長，而且又負傷了，所以這個位置就留給了他。他離開他的夥伴之前，承諾他一定不知疲倦儘快趕到印度，並且如果有必要，他會到里斯本面見國王，請求派遣大船到馬薩瓦把他們接出去。他們知道，他們面臨的是餘生都被困在衣索比亞，因為奧斯曼土耳其人正逐漸控制紅海，馬薩瓦隨時都有可能被佔領。
當船起錨時，卡斯塔尼奧索看到岸上的人跪下來朝著他們旗幟上的十字架禱告，然後騎上他們的馬和騾子。從外海這邊，他看到他們緩緩騎回內陸。