六七年來，我因為這個問題十分焦慮，以我最大的能力去說明，如何才能通過在更多的國家宣揚上帝的聖名和我們神聖的信仰，最大限度地為我主服務……在那些值得信賴和有智慧的歷史學家的著作中，我們還必須去尋找預言的留存財富。他們說在那些地方會發現巨大的財富。
——克里斯托弗·哥倫布（寫給西班牙國王斐迪南和女王伊莎貝拉的一封信，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個世紀也很難被辨識了。