После взятия Милана в одном из его соборов нашли якобы мощи трех царей-волхвов, пришедших с Востока и связанных с царством пресвитера. Они были с триумфом перезахоронены в Кельне – священном городе германских королей. Вскоре в города Аахене, где находилась гробница Карла Великого, была совершена церемония беатификации (причисления к лику святых) этого франкского императора. Но Фридриху Барбароссе необходим был ныне живущий царь-первосвященник. А тут императору удалось закончить многолетнюю войну с гвельфами на приемлемых условиях. Заключение мира ускорил и проект Третьего крестового похода (1189–1192). В походе участвовали также английский король Ричард Львиное Сердце и французский король Филипп II. Барбаросса надеялся, что, разгромив с помощью мощной армии курдского правителя Египта Саладдина (Салах-ад-дина), отнявшего у Запада Иерусалим, он сможет продвинуться дальше на восток и встретить пресвитера Иоанна, который поможет германскому императору сломить всех врагов и стать единоличным главой западного мира. Однако «Господь посрамляет высокоумие мудрецов». Барбаросса погиб, находясь в гостях у своего союзника князя Льва, правителя Киликийской Армении (юг Малой Азии). Согласно общепринятой версии, немолодой император утонул, купаясь в горной речке.
Однако вера людей в существование неподвластного возрасту правителя и его чудесного царства осталась непоколебимой. С падением владений крестоносцев в Палестине слухи о пресвитере Иоанне утихают, но они возрождаются с появлением авангарда армии Чингисхана в Персии и Армении. Когда монголы в XIII веке вторглись в Палестину, христиане, населявшие остатки государств крестоносцев, верили, что Чингисхан был пресвитером Иоанном, пришедшим спасти их от мусульман. Иногда пресвитером Иоанном считали Торгул-Хана, несторианского правителя, побежденного Чингисханом. Монгольского хана Хулагу также считали то пресвитером Иоанном, то сыном его Давидом, а монголов – христианами.
Справедливости ради стоит отметить, что к этому времени в Средней Азии уже была богатая история христианства. Католические миссионеры, ездившие ко двору Чингисхана в Каракорум, а также позднейшие путешественники в течение долгого времени разыскивали в Азии пресвитера Иоанна. Плано-Карпини отводит ему место в Индии; Рубрук считает его государем разбитых Чингисханом каракиданей, смешивая Чингисхана с Ван-ханом кераитским. Марко Поло находит потомков первого пресвитера Иоанна в лице монгольских князьков, несториан, кочевавших в стране Тянь-дэ, или Тендух, в Орд осе. Монте-Корвино и Одорик Фриульский вторят мнению Марко Поло.
Но поиски заветного царства оказались безуспешными, и потому в 1487 году португальский король Иоанн II командировал Педро да Ковильяна (Петра Ковиллания) и Альфонса Паиву в новую экспедицию. Она прибыла в Абиссинию, где большинство населения исповедовало ориентальное православие монофизитского толка, и признала местного царя пресвитером Иоанном (очевидно, из-за нетипичного для региона христианского