六七年来，我因为这个问题十分焦虑，以我最大的能力去说明，如何才能通过在更多的国家宣扬上帝的圣名和我们神圣的信仰，最大限度地为我主服务……在那些值得信赖和有智慧的历史学家的著作中，我们还必须去寻找预言的留存财富。他们说在那些地方会发现巨大的财富。
——克里斯托弗·哥伦布（写给西班牙国王斐迪南和女王伊莎贝拉的一封信，1499年）
1481年之后，葡萄牙向外探险的步伐发生了变化，因为若昂二世在那年登上王位。作为一个年仅16岁的王子，他因阿尔齐拉的大屠杀而欢欣鼓舞，但是10年后，事实证明他滥用权力激起的愤恨是难以平息的。在国内，他公开向那些曾使他懦弱的父亲屈从的贵族发起挑战；在国外，他手段灵活，特别是改善了与英国的原有关系。最重要的是，他命令轻快帆船应当再次起航，大胆地向南半球行进。船长们开始制订计划，沿着非洲海岸航行了一程又一程。若昂二世将大臣们的任何怀疑都搁置一旁。
葡萄牙一直都保持着这份自信。1483年，船长迪奥戈·卡姆带领一只轻快帆船抵达6度以南，到达一条大河——刚果河——的河口。河水从非洲内陆奔腾而来，侵蚀出一条从岸边延伸出很远的棕色道路，最终勉强汇入大西洋。对葡萄牙水手而言，这条河似乎提供了一条通往“埃塞俄比亚”和印度的道路，所以他们在海岬上竖起一块石柱，在上面刻上祖国的徽章。沙滩和急流毁灭了他们的希望，但是卡姆的确发现了一个组织有序的非洲王国，它就位于河流的南边。1485年，他第二次到达刚果，带着若昂二世送给刚果国王恩济加·恩库武的大量礼物，并且好意劝他投入基督教的怀抱。这种没有欧洲君主直接参与的友谊表示，似乎是将在印度发生的事情的一种前兆：刚果国王的儿子接受了洗礼，教名是阿方索；葡萄牙培训了黑人教士，还从里斯本派出了成群的工匠，以便帮助他们的新朋友。（重要的是，早期的承诺并没有被兑现，因为刚果王国很快就遭受了奴隶贸易的蹂躏。）
若昂二世的远航决心得以维持，同样是由于航海技术取得了显著进步，这使得轻快帆船即便在看不到北半球指向星、赤道以南很远的地方，也能够精确计算出纬度。若昂二世向犹太天文学家和数学家求助，特别是西班牙萨拉曼卡的著名教授亚伯拉罕·扎库托。这位教授发明了一种表格，能够给出一年中每天太阳在每一个纬度的最大高度。这些计算结果最初是用希伯来语写成的，之后被译成拉丁语，最后还被译为葡萄牙语，名为《天文法则》（citeoregimentodoastrolabio/cite）。若昂二世派他的私人医生约瑟夫航行去几内亚测试那些数据是否正确，约瑟夫报告说扎库托的计算准确无误。
若昂二世意识到巅峰时刻即将来临，这离他的曾祖父带领葡萄牙人占领休达、开始踏上非洲的土地，已过去了将近70年的时间。他已用井然有序的头脑仔细思考如何对待他唯一认识的统治者——“卡利卡特王侯”。一个叫作哥伦布的热那亚人住在葡萄牙，他于1484年来到里斯本的宫廷，建议由他率领一支船队向西穿过大西洋，寻找印度。他的建议被回绝，之后他转向西班牙，这反映出若昂二世的自信，他认为自己的轻快帆船快要取得成功了。
使得计划放缓的持续阻碍是人力的缺乏。甚至为了凑齐航行去几内亚的船只上的人，葡萄牙都不得不从欧洲其他地区招募亡命之徒。这些亡命徒能够胜任他们的任务，因为轻快帆船接下来面对的就只有配备了矛和箭的黑人异教徒，他们的武器与葡萄牙人锻造精良的火枪比起来不堪一击。然而，在印度洋，他们的敌人要可怕得多，而且葡萄牙人孤军奋战，他们位于航线的一端，面对的是数千里格风浪狂暴的海域。教皇告诉若昂二世要“从背后拿下奥斯曼土耳其人”。但是征服埃及和阿拉伯半岛之后，土耳其人已经逼近印度；到15世纪80年代，他们正沿着黑海向波斯前进，他们在地中海的表现也证明他们在海上使用枪炮可以和在陆地上使用得一样可怕。“从背后拿下奥斯曼土耳其人”不是一件容易的事情。
没有丝毫获胜的可能，又非常缺少人力，葡萄牙人被迫将代表基督教世界席卷东方的英雄幻想放置一旁。另一个选择就是作为谦卑的商人前往印度，只要有机会，就买下成船的香料。但是对于这种平凡角色，若昂二世从来不予仔细考虑，因为他执拗地相信，面对“错误的先知穆罕默德”的追随者，葡萄牙不会孤军奋战。
若昂二世精于世故又冷酷无情，可能会得到同是文艺复兴时期的人物马基雅维利的欣赏，他被葡萄牙臣民称为“完美的国王”。但是，他也完全相信祭司王约翰正在印度急切地等待与欧洲的基督教世界建立合作关系，他是一个虚构的东方祭司王。葡萄牙人可以信赖这种传说中的人物，因为他们将虚构的故事置于可证实的事实之上的喜好，在那个时候还很盛行。科学的想法没有点金术、魔法或者神迹来得重要。
祭司王约翰的故事是中世纪历史最悠久的传说之一，编造这样的故事是为了在意志薄弱的时候支撑宗教斗志，以文字谎言给予信徒新的宗教动力。“完美的国王”乐于相信这个编造的故事，说明他的梦想在这个时候达到顶峰，而且它能影响历史的进程。它的直接影响是欧洲人发起对亚洲的海上袭击，也间接导致向西航行发现了新世界。最后，它甚至是以这种稀奇的方式为自己辩护。
这个故事的起源可以追溯到一个传说：杜撰出来的“印度人的首领”对罗马所做的一次访问。这个故事是在1144年由杰布莱的休传播的，他是一个生于法国、住在黎凡特的天主教主教。他讲了一个叫作约翰的祭司王的故事，他说约翰住在“波斯和亚美尼亚以东很远的地方，他及其所有的臣民都是基督教徒，只不过是景教徒”。这位勇敢的统治者与波斯人作战，并且击败了他们。
之后不久，这个重要的、被创造出来的神话就以不同面目出现了：祭司王约翰写给教皇的一封信，还有他写给拜占庭的皇帝曼努埃尔和罗马人的皇帝腓特烈的信。所有的证据都表明这是由美因茨的一个基督教大主教捏造的，他宣称他将这些书信从希腊文译成了拉丁文。这些书信的希腊文原件从未被找到，而这个主意有可能是这位大主教在拜访君士坦丁堡期间偶然想到的。
一封伪造的信件讲到祭司王约翰的疆域，说那里有水晶构成的水域、大量珍贵的宝石，以及大片胡椒树林。在一座火山上，火蜥蜴在纺线，这些线将被用来制作珍贵的皇室服装。祭司王约翰讲到他美丽的妻子们，说他如何节制自己，每年只与她们发生四次关系，在其他时间他睡在一张“寒冷的蓝宝石床”上，以抑制自己的欲望。
祭司王约翰说，他的宫殿外面有一面魔镜，他能从中看清他的敌人的所有阴谋。这封信结尾语句的风格与圣经类似，十分华丽：“如果你数不清天上的星星和海中的沙子，你就无法了解我们王国的广阔和力量的宏大。”这样的想象利用了欧洲对亚洲潜在力量的模糊概念。
对这位基督教大主教的一种辩护是如果他的确是这些信件的作者，这些虚构的信件在中世纪则是一种可以被接受的文学形式。而使得伪造的祭司王约翰的信件在欧洲具有说服力的原因是在国王、教士以及农民中普遍存在希望它是真实的渴望。在十字军东征开始变得不顺利，所有的祷告者都祈求上帝干涉以拯救他们，而这些努力都是徒劳的时候，这个故事恢复了宗教与勇猛之间的纽带。这位神秘的长老是那些主教的东方同行，他被想象成与欧洲人一样，拳头都包有锁甲，手持钉头锤，骑马加入战斗。他还极为富有，使得教皇和大主教都把他视为和他们有一样信仰的人，而他所传递的信息其实可能与耶稣对贫穷和谦卑的要求相违背。
少数几个像哲学家罗杰·培根一样的勇士，公开表示对这个故事的怀疑，暗示祭司王可能并不存在。但是他们的呼声被忽略了。很快，人们就将这封信件从拉丁文译成几乎每一种欧洲语言和方言，甚至还有一个希伯来语版本。之后，抄写员开始把他们自己的想象加入其中。下一个阶段是编造假想的旅行者拜访神圣君主的故事，甚至还有与神圣君主的对话。自然地，所有前往东方的旅行者，特别是教会派往中国的修士，都被告知要去寻找祭司王。他们一回国就会被询问：是否真的见到他了，或者至少是否听说过他？很少有人敢说没有。
马可·波罗以令人沮丧的方式润色了这个故事，他说祭司王约翰已经去世很久了，他是被蒙古人的领袖成吉思汗在“迄今为止见过的最大的某次战斗中”杀死的。祭司王虽然是一位基督徒，但他曾是一个蒙古人。马可·波罗将他变成了一个不太招人喜欢的人物，他的傲慢自大导致了自己的垮台。当成吉思汗礼貌地问他是否能娶他的女儿时，祭司王约翰激烈地回答说他宁愿“把他的女儿扔到火里”。这些事情最终导致了一场灾难性的战争。祭司王约翰的儿子是乔治国王，他只是大汗的一个封臣。
即使马可·波罗的记述十分混乱，但是关于这件事仍有一个确切的历史依据，因为1141年在撒马尔罕附近的卡特万峡谷的确发生了一场大战，交战双方是来自中国北方、游牧民耶律大石的追随者，以及塞尔柱苏丹桑伽的穆斯林军队。据说交战双方在战场上一共投入了40万骑兵，而且耶律大石在获得胜利之后攻占了撒马尔罕。尽管他不是基督教徒，但是他取得了异教徒景教徒的支持，他对景教徒也充满同情（甚至给他的一个儿子取了一个恰当而又好战的名字——以利亚）。可能是景教徒商人将耶律大石胜利的消息向西传到了黎凡特，因为就在3年后杰布莱的休主教旅行到了罗马,在那儿他讲述了一位叫作约翰的基督徒国王是如何“在最东端”获得伟大胜利的。
如果在14世纪初马可·波罗就宣称祭司王约翰去世了，用任何理性来判断，他也必然是去世了，欧洲人不再相信祭司王约翰的时间似乎就要到来。但是相反，他的名声通过另一个名字得到了新生，即“约翰·曼德维尔爵士”，他是一个虚构的英国骑士，根据一本杜撰的回忆录，他在东方旅行了34年。
关于曼德维尔回忆录的作者，至今还是一个谜，但他是一个聪明绝顶的人。他可能是一位英国人，出生在伦敦北部的圣奥尔本，犯了重罪之后，在1350年左右穿过海峡逃到了另一个教堂城——列日。也许他是一个珠宝商，因为他的叙述表明他对钻石有极强的兴趣。他去世于1372年，在此之前几年，他完成了一本七万字的杰作，该书是用法语写成的。在他临终前，有一个叫作让·杜特勒姆斯的列日律师，他同时也是一位作家，有时候被误认为是曼德维尔回忆录的作者。
虚构的约翰爵士的姓氏，可能取自12世纪的一个十字军战士——埃塞克斯伯爵威廉·德·曼德维尔。他与一支由37艘船构成的舰队一起，从英国航行前往圣地。（在远航途中，他在一场战斗中帮助葡萄牙人对抗穆斯林，这场战斗共有4万人被杀死。）虽然曼德维尔回忆录的作者隐藏了自己的真实身份，但这不影响这部作品在长达几个世纪的时间里对欧洲社会的各个阶层产生影响。人们并不认为他是一个善于剽窃真正旅行家的回忆录的聪明骗子，其中也包括马可·波罗的游记，而是将他视为一个值得尊敬和可以信赖的世界奇观的见证者。
1470年，这本回忆录的荷兰语版问世，《曼德维尔旅行记》注定成为欧洲第一本以拉丁文之外的语言印刷的书籍。到1500年，这本书的版本至少已经出现了25个。这本书的成功部分是由于它的故事十分奇异，有时还带有一些性的因素，甚至还会加工一些欧洲人所熟知的罗马和中世纪的故事，例如，有个地方的男人会邀请其他男人和他们的妻子睡觉。教会谴责了这种粗鄙又世俗的写作方式，但是从未成功将它宣布为不合法。它的作者知道如何预先防止宗教批评：当故事发展到高潮时，读者们会看到最有道德的基督徒君主祭司王约翰的国度。
最初祭司王约翰的信件的作者动机很好理解。他想要告诉陷入困境的欧洲基督徒，他们不是孤独的，救援可能很快就会到来。而他自称约翰·曼德维尔爵士的动机则更加具有迷惑力，因为这样做几乎没有什么经济回报。也许他只是一个“足不出户的旅行者”，在生命的最后时日里，他将自己一生阅读过的有趣故事汇集起来，聊以自娱。的确，故事最后的话语是令人哀伤的，他讲到“风湿性痛风”，还提到“在痛苦间隙才会感到一丝舒适”。他请求读者们为他祈祷，而他也会为他们祷告。如果这部作品含有一些宗教或者政治动机，时隔6个世纪也很难被辨识了。