如果能活着亲眼看见，《曼德维尔旅行记》的作者一定会对他的作品取得的巨大而持久的成功感到惊奇。一个必然的结果是祭司王约翰的神话会在那些欧洲当权者的头脑中持续下去，特别是葡萄牙人，他们正在为胡椒、香料以及珠宝寻找新的前往印度洋国家的路线。寻找祭司王是对上帝的效忠，而获得世俗的财富也一样。因此，一个中世纪的神话注定要支持大航海时代的需要，甚至是穿越大西洋寻找日本和大汗国土的哥伦布，也仔细地研究过曼德维尔。但是哥伦布很有可能不想遇见祭司王约翰，因为曼德维尔已经将祭司王置于马可·波罗过去安置他的地方的西边，他是“伟大的印度王”。而且，这位难以捉摸的君主的名字已经不再被认为属于个人，否则就显得过于轻信了。
所以，祭司王约翰成为在东方发现的任何适合的基督教王国统治者的一个称号。这个称号在曼德维尔的故事里就是这样被使用的：“祭司王约翰总是娶大汗的女儿为妻，而大汗也总是娶祭司王约翰的女儿为妻，因为他们两个是天底下最伟大的国王。”（这反映了欧洲人对亚洲所发生事件的无知，曼德维尔故事的作者似乎不知道蒙古的统治者“大汗”在他写作之前近一个世纪就下台了。）
早在1306年，曼德维尔故事的作者还没有动笔之前，一位学者就已经提出，埃塞俄比亚是祭司王约翰的王国。这是因为埃塞俄比亚曾派遣一支由30人组成的代表团，他们对欧洲的访问引人注目。他们觐见教皇和“西班牙国王”，为的是寻求帮助以对付穆斯林。他们在所有的欧洲国家中选择西班牙，是因为亚历山大里亚有一个活跃的加泰罗尼亚贸易站，而且从传统上来讲，亚历山大里亚的东正教牧首可以任命埃塞俄比亚教会的领袖。埃塞俄比亚人说，如果能获得西班牙人的援助，他们随时准备加入对抗异教徒的战争。
除了受到友谊的表示，埃塞俄比亚使团的收获甚微，但是在他们从罗马和阿维尼翁归国的途中，他们受到教皇克莱蒙五世的接待，并且因为糟糕的天气在热那亚耽搁了一段时间。一位叫作乔瓦尼·达·卡里尼亚诺的博学的教士，利用这个机会询问了这些外表与众不同的陌生人一些问题。作为一个制图者，他对自己能够获得的所有有关埃塞俄比亚地理，以及风俗和宗教仪式的知识都十分感兴趣。按照乔瓦尼的说法，埃塞俄比亚的国王就是祭司王约翰。由于这些拜访者从来没有称呼自己的国王为祭司王约翰（他的名字是韦德姆·阿拉德），这个称号一定是卡里尼亚诺给他取的。因为那时候人们认为祭司王约翰在印度，而埃塞俄比亚一般被称作中印度，所以这是一种合理的假设。
另一个认为这位传奇的基督徒国王在印度的人，是来自法国南部城镇塞维拉克多明我会的一个修士，此人叫作若尔达努斯。我们对于他的生平不是很清楚，但是按照他自己的记述，他在14世纪早期曾两次前往东方冒险，并被他所属的教会授予“大印度哥伦布姆的主教”头衔。（若尔达努斯所谓的“大印度”，可能包括印度南部、斯里兰卡和泰国；而哥伦布姆是指卡利卡特附近的奎隆港。）
据说早在圣托马斯的时代，印度南部就有基督徒社群。圣徒是在公元52年前往印度传播福音的，并且最终在那里逝世。若尔达努斯被派往那里是去哄骗那些固执的信徒信奉罗马公教，以及获得更多新的信徒。所有的证据都表明他收效甚微，而且尽管祭司王约翰和圣托马斯的故事经常被混为一谈，但是这位富于冒险精神的多明我会修士失望地发现，大印度根本没有一丝基督徒国王的踪迹。
祭司王约翰应该在其他地方，若尔达努斯一回家，就自信地指认埃塞俄比亚为祭司王的王国。虽然没有宣称自己去过埃塞俄比亚，但是这位天主教修士却到过“大阿拉伯半岛”，在那里他了解到埃塞俄比亚人“全都是基督徒，只不过是持异端者”。他对寻找怪兽很感兴趣：“埃塞俄比亚是一个非常大的国家，而且非常热。那里有很多怪兽，例如守护金山的格里芬……我认为那个国家的国王比世界上其他任何国家的国王都更有可能是祭司王约翰，而且更加富有。他拥有很多黄金、白银和珍贵的宝石。据说还有52个国王隶属他的统治。”若尔达努斯还描述了东非，他称之为“第三印度”。那里还有喷火的龙，凶猛到能够杀死一头大象的独角兽，以及“又黑又矮又胖的人”。
若尔达努斯在1330年对埃塞俄比亚所做的描述，将祭司王约翰的传说与真实的类似情况关联起来，这是一个至关重要的进步。他在旅途中得到过热那亚商人的帮助，对于这一点几乎确定无疑。1339年，在一幅由热那亚人安杰利诺·达·达尔奥尔托绘制的地图上，写着努比亚的穆斯林“正与努比亚和埃塞俄比亚的基督徒持续不断地发生战争，而后者由黑人基督徒祭司王约翰统治”。
最后，欧洲人在整个亚洲到处寻找的祭司王约翰的王国定在了非洲。虽然这个现实比300年来的夸大叙述要卑微得多，但是这足以使葡萄牙人心怀虔诚和商业计划，顺着同样乐观的风向向前航行。
***
15世纪，居住在埃塞俄比亚的欧洲人有一小块殖民地。那儿的大多数人是意大利人，主要来自威尼斯、佛罗伦萨和热那亚。有些人前往“祭司王约翰的国家”是希望得到珍贵的宝石；其他人则试图通过尼罗河和红海到达印度洋，但却困在了那些地方。最早期的拜访者中有一个人的名字流传了下来，他叫作彼得罗·兰布罗，有时候被称为“那不勒斯的彼得罗”（实际上，他来自西西里的墨西拿，后来它成为那不勒斯的一部分）。兰布罗在1407年到达埃塞俄比亚，那时候他还是个年轻人，到那儿不久他就娶了一位当地女子，并在那里居住了40年。
他对于欧洲与埃塞俄比亚关系的影响是巨大的，这一点在1428年埃塞俄比亚使团觐见阿拉贡的阿方索五世时第一次体现了出来。埃塞俄比亚人的目的和1306年的时候一样，还是想要接近西班牙的统治者，而这最有可能是由于兰布罗的游说，因为阿方索拥有西西里，而且即将得到那不勒斯。使者们以派他们前来的国王伊沙克的名义，提议两个王室应该联姻：阿方索应该派他的一个儿子迎娶埃塞俄比亚公主，而埃塞俄比亚王子会迎娶阿方索的一个女儿。阿方索回避了这个提议，但是确实答应派遣一队工匠（他们均死于途中）。
根据相关记载，两年后兰布罗陪同一支代表团前往埃塞俄比亚，该代表团是由与西班牙有关系的贝里公爵派出的。1432年，兰布罗在君士坦丁堡附近停留，在那里遇到了勃艮第旅行者贝特朗东·德·拉布罗基耶。由于使团的其他成员都死了，毫无疑问兰布罗想要至少再招募一个欧洲人，以便到时候一起觐见埃塞俄比亚的君主。他“使尽浑身解数”，诱使拉布罗基耶与他一起去埃塞俄比亚的首都阿克苏姆。尽管这个勃艮第人在他的回忆录里提到他之前见过兰布罗（没说在哪里），但是对于“那不勒斯的彼得罗”捏造类似埃塞俄比亚人计划改道尼罗河、饿死埃及人之类的骇人听闻的故事，他很不欣赏。最终，彼得罗的提议被拒绝了。
出使西班牙的失败，没有减少兰布罗对埃塞俄比亚的新国王扎拉-雅各布的支持，因为他接下来的外交使命是前往印度和中国。1450年，带着埃塞俄比亚一个叫作布拉泽·米凯莱的使臣，他又被派往欧洲，时隔20年，他再次得到阿拉贡的阿方索的接见。
兰布罗利用这次机会访问了自己的出生地。在那不勒斯，他接受了一个多明我会修士的访问。这个修士简短地记录了他令人感兴趣的职业生涯。修士还描绘了兰布罗的外貌，说他高个子，皮肤被太阳晒得黝黑，打扮精致且一头白发。这是历史所能提供的对兰布罗的最后一瞥。
兰布罗的幸运之处是他经常被允许离开埃塞俄比亚，而其他来到埃塞俄比亚的外国人则不被允许离开。扎拉-雅各布对他们很好，赠给他们妻子和土地，但是拒绝让他们离开。他可能是害怕他们在路上被穆斯林抓住和折磨，进而供出战争中的重要信息。他的“囚犯们”是不可能逃出去的，因为出去的路只有一条，那就是向北到达红海边上的马萨瓦港，而那条路充满危险并且被严密把守。
葡萄牙人收集的关于这个国家的信息是如此支离破碎，以致于他们坚信曼德维尔关于祭司王约翰战无不胜的故事：“这位国王与其他任何领主作战的时候，在他的前方都不用打旗帜，但是他有3个巨大的、镶满珠宝的黄金十字架。每个十字架都被放在一辆装饰华丽的战车上，每个十字架都有指定的1万甲兵和10万多名步兵保护。”
未被危险吓倒，几个方济各会的传教士成功地抵达了埃塞俄比亚，并且前往国王的宫殿。尽管一位威尼斯修士觉得有义务在记录这次旅行时提及“伟大的祭司王约翰”，但是他对埃塞俄比亚的评价显然是比较低的：
这个国家的黄金很多，但谷物稀少，酒也比较缺乏。它的人口非常多，而且这里的人粗俗鄙陋、没有文化。他们没有作战用的铁制武器。弓箭和长矛是用藤条制作的。如果没有20万或者30万人，国王是不会上阵的。每年他都会为信仰而战。他不会付钱给那些上战场的战士，但是会提供给他们生活所需，并且免除这些战士的每一种皇家赋税。所有的战士都是被挑选出来的，他们的手臂上烙刻有皇家印章。没有人穿羊毛衣服，因为他们没有这种布料，他们穿的是亚麻服装。无论男人还是女人，腰部以上都是赤裸的，而且他们全都光脚；他们总是浑身长满了虱子。他们是一个脆弱的民族，缺少精力、没有用处，只有骄傲。
将穆斯林向红海驱逐，扎拉-雅各布扩大了他的统治疆域，成为15世纪最强大的埃塞俄比亚统治者，如果他阅读了以上文字，将会对这些轻蔑的判断愤怒不已。扎拉-雅各布还经常对埃及耀武扬威，虽然他的威胁不太可能生效，但他的确经常宣称他要改道青尼罗河。在1443年一封写给开罗的信中，他警告埃及苏丹贾玛克他本来即将付诸行动，只是对上帝的恐惧和不愿使人民遭受不幸的怜悯之心使他克制住了自己。
扎拉-雅各布讨厌欧洲人称他为祭司王约翰，一再强调自己已经有一个完美的名字了，而且他的名字的含义是“雅各布的种子”。他不允许任何虔诚的行为：他的臣民们被命令放弃在额头上印上魔鬼的纹身的行为，任何反对者都会身首异处。
葡萄牙人对这些事情知道多少，我们并不清楚。但是这足以使他们确信，祭司王约翰确实存在。他的埃塞俄比亚王国的确切位置仍不清楚，但是它一定是前往印度途中能提供救助之地。无论在非洲何处登岸，所有轻快帆船的船长都被要求搜寻这位基督徒国王的信息。因为在毛罗的地图上，几乎整块大陆都被勾描成点缀着想象出来的城市和图景的埃塞俄比亚，所以里斯本的王室开始思考获得这块大陆更多精确信息的方法。