Onun var olduğuna dair hiçbir kanıt bulunmamasına rağmen, doğuda bir Hristiyan imparatorluğunun akıl almaz derecede güçlü ve zengin hükümdarına duyulan inanç yüzyıllar boyunca sürdü ve kâşifleri harekete geçirdi.
1145'te Alman piskopos Freisingli Otto, tarih ve felsefe alanındaki etkili eseri Chronica'yı yayımladı; eserinde çok uzak doğudaki bir diyarın Hristiyan hükümdarından söz etti. Bu rahip-kral, savaşta Müslümanları yenmiş ve Kudüs'ü ele geçirmek için yola çıkmış, ancak ordusunu Dicle Nehri'nin karşı kıyısına geçirememişti.
Bu, Orta Çağ Avrupası'nın önemli bir figürü olan Rahip Yuhanna'ya dair bilinen ilk yazılı göndermedir; ne var ki hiç var olmamıştı.
Yirmi yıl sonra, 1165'te, Bizans imparatorunun sarayında gizemli adamdan, yani “üç Hint diyarının yüce hükümdarından” geldiği iddia edilen bir mektup ortaya çıktı. Uzun mektubunda kendisini şöyle tanıttı: “Ben, Rahip Yuhanna, efendilerin efendisiyim ve gökyüzünün altındaki bütün zenginliklerde, erdemde ve güçte engin dünyanın bütün krallarından üstünüm.”
O, 72 krallığın barış içinde yaşadığı, bütün suç ve ahlaksızlıkların ortadan kalktığı geniş bir imparatorlukta hem kral hem de dinî lider olarak hizmet eden dindar bir Hristiyandı (Rahip unvanı din adamı anlamına gelir). Zenginlikler boldu; nehirler kelimenin tam anlamıyla değerli taşlarla akıyor, anka kuşu ve tepegözler gibi mitolojik yaratıklar serpilip gelişiyordu.
Mektup yalnızca yeryüzünde keşfedilebilecek bir Hristiyan cennetini değil, aynı zamanda Batı Avrupa'nın Haçlı Seferleri'nde Müslüman kuvvetlere karşı savaşmak için çok muhtaç olduğu müttefiki de vaat ediyordu.
Katalan Atlası'ndan 14. yüzyıla ait bir görselde Marco Polo'nun Hindistan'a giden kervanı yer alır. Rahip Yuhanna'nın var olduğuna dair hiçbir kanıt bulunmamasına rağmen Polo ondan gerçek bir kişi olarak söz etmiştir.
Mektup, kimliği hâlâ bilinmeyen bir yazar tarafından yazılmış bir sahtekârlık ürünüydü; yine de geniş çapta dolaşıma girdi. Kısa süre içinde Rahip Yuhanna'nın adı ve ünü Avrupa'ya yayıldı; birçok kişi onu tamamen gerçek biri olarak görmekte hiçbir sakınca görmedi. Papa III. Aleksander, doğudaki bu buyurgan krala bir mektup iletmeye çalışmak üzere bir elçi bile gönderdi.
Avrupalılar uzun süredir doğuda Hristiyan krallıkların olması gerektiğine inanıyordu ve bu inanç temelsiz değildi. Gerçekten de Asya'nın dört bir yanında büyük Hristiyan toplulukları vardı. Mesih'in doğumunda onu ziyaret eden üç bilge kraldan, yani Müneccim Krallar'dan birinin soyundan geldiğini iddia eden Rahip Yuhanna'nın Nasturilik adı verilen bir mezhebe mensup olabileceği düşünülüyordu.
İslam dünyasının ötesine dair sınırlı coğrafya bilgisi, Avrupalıların orada kimlerin yaşadığını ve nasıl insanlar olduklarını bilmemesi anlamına geliyordu; öyleyse neden geniş bir imparatorluğun Hristiyan hükümdarı olmasın? Rahip Yuhanna imgesini büyütecek yeterince gerçeklik kırıntısı da vardı: Avrupa'da varlıklarını hissettiren Müslüman olmayan halklar, yani Moğollar gerçekten de vardı.
Rahip Yuhanna'nın varlığının çok güçlü biçimde sorgulanmamasının belki de en önemli nedeni, Avrupalıların ona inanmak istemesidir. Haçlı Seferleri'nin gidişatını değiştirecek bir müttefik olasılığına tutunmak istiyorlardı; ihtiyaç en çok duyulduğunda bu müttefik hatırlanacaktı.
Beşinci Haçlı Seferi'nin felaketinin ardından Ptolemais Piskoposu Jacques de Vitry, papaya iyimser ifadelerle yazdı ve Müslümanların, Hindistan Kralı olan ve Rahip Yuhanna'nın soyundan gelen Davut tarafından saldırıya uğradığını anlattı. Tarihçiler, bu anlatının Cengiz Han'dan esinlenmiş olabileceğini öne sürmüştür.
Rahip Yuhanna'nın hikâyesi, yıllar boyunca birçok gezgini ve misyoneri bilinmeyene doğru yola çıkmaya ve bir süre Hindistan'da olduğu düşünülen, neredeyse büyülü krallığını bulmaya teşvik etti. Marco Polo 13. yüzyılın sonlarında seyahate çıktığında hiçbir şey bulunamamıştı, ancak o yine de Rahip Yuhanna'dan bölgedeki gerçek bir figür olarak söz etti.
1573 tarihli bir harita, Rahip Yuhanna'nın efsanevi Hristiyan imparatorluğu olarak ün salan Habeşistan'ı gösteriyor.
Ancak Rahip Yuhanna'nın mektubunda anlatılan büyüklük ve güçte bir Hristiyan imparatorluğunun bulunmadığı giderek daha açık hâle geldikçe, hikâye kralı Afrika'ya, özellikle de dördüncü yüzyıldan beri bir Hristiyan topluluğunun var olduğu Etiyopya'ya yerleştirecek şekilde değişti.
14. yüzyıldan itibaren Etiyopya'dan gelen elçilikler İtalya'ya gitti ve Roma'da varlık gösterdi; Avrupalılar da hızla onların liderinin Rahip Yuhanna olması gerektiği sonucuna vardı. Onun ülkesinin Nil'in kaynağını barındırdığı ve nehrin yatağını değiştirerek Mısır'da büyük yıkıma yol açma gücüne sahip olduğu anlatıları ortaya çıktı.
Portekizliler, Afrika'yı keşfetmeye büyük kaynaklar ayırdı; bu durum Vasco da Gama'nın 1497-99 yılları arasında Ümit Burnu'ndan dolanarak Hindistan'a yaptığı ve dünyayı değiştiren yolculuğuna yol açtı. Bu çabaların önemli bir kısmını, Rahip Yuhanna'yı kesin olarak bulma amacı körüklüyordu. Etiyopya'da Hristiyan bir hükümdar buldular, ancak bunun her şeye gücü yeten ve olağanüstü zengin olan Rahip Yuhanna olmadığı açıktı.
