如果能活著親眼看見，《曼德維爾旅行記》的作者一定會對他的作品取得的巨大而持久的成功感到驚奇。一個必然的結果是祭司王約翰的神話會在那些歐洲當權者的頭腦中持續下去，特別是葡萄牙人，他們正在為胡椒、香料以及珠寶尋找新的前往印度洋國家的路線。尋找祭司王是對上帝的效忠，而獲得世俗的財富也一樣。因此，一箇中世紀的神話註定要支援大航海時代的需要，甚至是穿越大西洋尋找日本和大汗國土的哥倫布，也仔細地研究過曼德維爾。但是哥倫布很有可能不想遇見祭司王約翰，因為曼德維爾已經將祭司王置於馬可·波羅過去安置他的地方的西邊，他是「偉大的印度王」。而且，這位難以捉摸的君主的名字已經不再被認為屬於個人，否則就顯得過於輕信了。
所以，祭司王約翰成為在東方發現的任何適合的基督教王國統治者的一個稱號。這個稱號在曼德維爾的故事裡就是這樣被使用的：「祭司王約翰總是娶大汗的女兒為妻，而大汗也總是娶祭司王約翰的女兒為妻，因為他們兩個是天底下最偉大的國王。」（這反映了歐洲人對亞洲所發生事件的無知，曼德維爾故事的作者似乎不知道蒙古的統治者「大汗」在他寫作之前近一個世紀就下臺了。）
早在1306年，曼德維爾故事的作者還沒有動筆之前，一位學者就已經提出，衣索比亞是祭司王約翰的王國。這是因為衣索比亞曾派遣一支由30人組成的代表團，他們對歐洲的訪問引人注目。他們覲見教皇和「西班牙國王」，為的是尋求幫助以對付穆斯林。他們在所有的歐洲國家中選擇西班牙，是因為亞歷山大里亞有一個活躍的加泰羅尼亞貿易站，而且從傳統上來講，亞歷山大里亞的東正教牧首可以任命衣索比亞教會的領袖。衣索比亞人說，如果能獲得西班牙人的援助，他們隨時準備加入對抗異教徒的戰爭。
除了受到友誼的表示，衣索比亞使團的收穫甚微，但是在他們從羅馬和阿維尼翁歸國的途中，他們受到教皇克萊蒙五世的接待，並且因為糟糕的天氣在熱那亞耽擱了一段時間。一位叫作喬瓦尼·達·卡里尼亞諾的博學的教士，利用這個機會詢問了這些外表與眾不同的陌生人一些問題。作為一個製圖者，他對自己能夠獲得的所有有關衣索比亞地理，以及風俗和宗教儀式的知識都十分感興趣。按照喬瓦尼的說法，衣索比亞的國王就是祭司王約翰。由於這些拜訪者從來沒有稱呼自己的國王為祭司王約翰（他的名字是韋德姆·阿拉德），這個稱號一定是卡里尼亞諾給他取的。因為那時候人們認為祭司王約翰在印度，而衣索比亞一般被稱作中印度，所以這是一種合理的假設。
另一個認為這位傳奇的基督徒國王在印度的人，是來自法國南部城鎮塞維拉克多明我會的一個修士，此人叫作若爾達努斯。我們對於他的生平不是很清楚，但是按照他自己的記述，他在14世紀早期曾兩次前往東方冒險，並被他所屬的教會授予「大印度哥倫布姆的主教」頭銜。（若爾達努斯所謂的「大印度」，可能包括印度南部、斯里蘭卡和泰國；而哥倫布姆是指卡利卡特附近的奎隆港。）
據說早在聖托馬斯的時代，印度南部就有基督徒社群。聖徒是在西元52年前往印度傳播福音的，並且最終在那裡逝世。若爾達努斯被派往那裡是去哄騙那些固執的信徒信奉羅馬公教，以及獲得更多新的信徒。所有的證據都表明他收效甚微，而且儘管祭司王約翰和聖托馬斯的故事經常被混為一談，但是這位富於冒險精神的多明我會修士失望地發現，大印度根本沒有一絲基督徒國王的蹤跡。
祭司王約翰應該在其他地方，若爾達努斯一回家，就自信地指認衣索比亞為祭司王的王國。雖然沒有宣稱自己去過衣索比亞，但是這位天主教修士卻到過「大阿拉伯半島」，在那裡他了解到衣索比亞人「全都是基督徒，只不過是持異端者」。他對尋找怪獸很感興趣：「衣索比亞是一個非常大的國家，而且非常熱。那裡有很多怪獸，例如守護金山的格里芬……我認為那個國家的國王比世界上其他任何國家的國王都更有可能是祭司王約翰，而且更加富有。他擁有很多黃金、白銀和珍貴的寶石。據說還有52個國王隸屬他的統治。」若爾達努斯還描述了東非，他稱之為「第三印度」。那裡還有噴火的龍，兇猛到能夠殺死一頭大象的獨角獸，以及「又黑又矮又胖的人」。
若爾達努斯在1330年對衣索比亞所做的描述，將祭司王約翰的傳說與真實的類似情況關聯起來，這是一個至關重要的進步。他在旅途中得到過熱那亞商人的幫助，對於這一點幾乎確定無疑。1339年，在一幅由熱那亞人安傑利諾·達·達爾奧爾託繪製的地圖上，寫著努比亞的穆斯林「正與努比亞和衣索比亞的基督徒持續不斷地發生戰爭，而後者由黑人基督徒祭司王約翰統治」。
最後，歐洲人在整個亞洲到處尋找的祭司王約翰的王國定在了非洲。雖然這個現實比300年來的誇大敘述要卑微得多，但是這足以使葡萄牙人心懷虔誠和商業計劃，順著同樣樂觀的風向向前航行。
***
15世紀，居住在衣索比亞的歐洲人有一小塊殖民地。那兒的大多數人是義大利人，主要來自威尼斯、佛羅倫薩和熱那亞。有些人前往「祭司王約翰的國家」是希望得到珍貴的寶石；其他人則試圖通過尼羅河和紅海到達印度洋，但卻困在了那些地方。最早期的拜訪者中有一個人的名字流傳了下來，他叫作彼得羅·蘭布羅，有時候被稱為「那不勒斯的彼得羅」（實際上，他來自西西里的墨西拿，後來它成為那不勒斯的一部分）。蘭布羅在1407年到達衣索比亞，那時候他還是個年輕人，到那兒不久他就娶了一位當地女子，並在那裡居住了40年。
他對於歐洲與衣索比亞關係的影響是巨大的，這一點在1428年衣索比亞使團覲見阿拉貢的阿方索五世時第一次體現了出來。衣索比亞人的目的和1306年的時候一樣，還是想要接近西班牙的統治者，而這最有可能是由於蘭布羅的遊說，因為阿方索擁有西西里，而且即將得到那不勒斯。使者們以派他們前來的國王伊沙克的名義，提議兩個王室應該聯姻：阿方索應該派他的一個兒子迎娶衣索比亞公主，而衣索比亞王子會迎娶阿方索的一個女兒。阿方索迴避了這個提議，但是確實答應派遣一隊工匠（他們均死於途中）。
根據相關記載，兩年後蘭布羅陪同一支代表團前往衣索比亞，該代表團是由與西班牙有關係的貝里公爵派出的。1432年，蘭布羅在君士坦丁堡附近停留，在那裡遇到了勃艮第旅行者貝特朗東·德·拉布羅基耶。由於使團的其他成員都死了，毫無疑問蘭布羅想要至少再招募一個歐洲人，以便到時候一起覲見衣索比亞的君主。他「使盡渾身解數」，誘使拉布羅基耶與他一起去衣索比亞的首都阿克蘇姆。儘管這個勃艮第人在他的回憶錄裡提到他之前見過蘭布羅（沒說在哪裡），但是對於「那不勒斯的彼得羅」捏造類似衣索比亞人計劃改道尼羅河、餓死埃及人之類的駭人聽聞的故事，他很不欣賞。最終，彼得羅的提議被拒絕了。
出使西班牙的失敗，沒有減少蘭布羅對衣索比亞的新國王扎拉-雅各布的支援，因為他接下來的外交使命是前往印度和中國。1450年，帶著衣索比亞一個叫作布拉澤·米凱萊的使臣，他又被派往歐洲，時隔20年，他再次得到阿拉貢的阿方索的接見。
蘭布羅利用這次機會訪問了自己的出生地。在那不勒斯，他接受了一個多明我會修士的訪問。這個修士簡短地記錄了他令人感興趣的職業生涯。修士還描繪了蘭布羅的外貌，說他高個子，皮膚被太陽曬得黝黑，打扮精緻且一頭白髮。這是歷史所能提供的對蘭布羅的最後一瞥。
蘭布羅的幸運之處是他經常被允許離開衣索比亞，而其他來到衣索比亞的外國人則不被允許離開。扎拉-雅各布對他們很好，贈給他們妻子和土地，但是拒絕讓他們離開。他可能是害怕他們在路上被穆斯林抓住和折磨，進而供出戰爭中的重要資訊。他的「囚犯們」是不可能逃出去的，因為出去的路只有一條，那就是向北到達紅海邊上的馬薩瓦港，而那條路充滿危險並且被嚴密把守。
葡萄牙人收集的關於這個國家的資訊是如此支離破碎，以致於他們堅信曼德維爾關於祭司王約翰戰無不勝的故事：「這位國王與其他任何領主作戰的時候，在他的前方都不用打旗幟，但是他有3個巨大的、鑲滿珠寶的黃金十字架。每個十字架都被放在一輛裝飾華麗的戰車上，每個十字架都有指定的1萬甲兵和10萬多名步兵保護。」
未被危險嚇倒，幾個方濟各會的傳教士成功地抵達了衣索比亞，並且前往國王的宮殿。儘管一位威尼斯修士覺得有義務在記錄這次旅行時提及「偉大的祭司王約翰」，但是他對衣索比亞的評價顯然是比較低的：
這個國家的黃金很多，但穀物稀少，酒也比較缺乏。它的人口非常多，而且這裡的人粗俗鄙陋、沒有文化。他們沒有作戰用的鐵製武器。弓箭和長矛是用藤條製作的。如果沒有20萬或者30萬人，國王是不會上陣的。每年他都會為信仰而戰。他不會付錢給那些上戰場的戰士，但是會提供給他們生活所需，並且免除這些戰士的每一種皇家賦稅。所有的戰士都是被挑選出來的，他們的手臂上烙刻有皇家印章。沒有人穿羊毛衣服，因為他們沒有這種布料，他們穿的是亞麻服裝。無論男人還是女人，腰部以上都是赤裸的，而且他們全都光腳；他們總是渾身長滿了蝨子。他們是一個脆弱的民族，缺少精力、沒有用處，只有驕傲。
將穆斯林向紅海驅逐，扎拉-雅各布擴大了他的統治疆域，成為15世紀最強大的衣索比亞統治者，如果他閱讀了以上文字，將會對這些輕蔑的判斷憤怒不已。扎拉-雅各布還經常對埃及耀武揚威，雖然他的威脅不太可能生效，但他的確經常宣稱他要改道青尼羅河。在1443年一封寫給開羅的信中，他警告埃及蘇丹賈瑪克他本來即將付諸行動，只是對上帝的恐懼和不願使人民遭受不幸的憐憫之心使他剋制住了自己。
扎拉-雅各布討厭歐洲人稱他為祭司王約翰，一再強調自己已經有一個完美的名字了，而且他的名字的含義是「雅各布的種子」。他不允許任何虔誠的行為：他的臣民們被命令放棄在額頭上印上魔鬼的紋身的行為，任何反對者都會身首異處。
葡萄牙人對這些事情知道多少，我們並不清楚。但是這足以使他們確信，祭司王約翰確實存在。他的衣索比亞王國的確切位置仍不清楚，但是它一定是前往印度途中能提供救助之地。無論在非洲何處登岸，所有輕快帆船的船長都被要求搜尋這位基督徒國王的資訊。因為在毛羅的地圖上，幾乎整塊大陸都被勾描成點綴著想象出來的城市和圖景的衣索比亞，所以里斯本的王室開始思考獲得這塊大陸更多精確資訊的方法。