Відомості про проповіді апостола Фоми століттями вселяли віру в те, що в далекій і таємничій Індії існує велика християнська держава, яким керує пресвітер Іоанн. Ця легенда дійшла і до Русі, де легендарний цар-священик перетворився в «царя і попа Івана».
Першою згадкою пресвітера Іоанна прийнято вважати запис в «Хроніці про двох градах» Оттона Фрейзінгенського. Під 1145 роком Оттон розповідає, що почув у Римі від єпископа Габалі історію про християнському правителеві з далеких земель Сходу. У другій половині XII в. легенда про пресвітера Іоанна набуває поширення завдяки псевдоепіграфіческому послання візантійського імператора Мануїлу Комнину (1143-1180) від пресвітера Іоанна. Під «Індією», правителем якої вважався пресвітер Іоанн, розумілася напівлегендарна країна, поміщають в різних частинах ойкумени, оскільки в середньовічній Європі побутувало уявлення про «трьох Индиях»; як правило, царство пресвітера Іоанна ототожнювалося з «Великої Індією». У початковому тексті послання пресвітер Іоанн називався правителем всіх трьох Індій (в тому числі і тієї, де знаходиться гробниця апостола Фоми) і володарем сімдесяти двох царів. Землі пресвітера Іоанна наповнені всілякими дивина і населені безліччю народів. Коли пресвітер Іоанн йде на війну, то перед ним несуть величезні хрести. Щороку він здійснює паломництво на могилу пророка Даниїла в Вавилонської пустелі. Протягом усього XIII століття мандрівники, місіонери і посли з Європи (Іоанн Плано Карпіні і Гійом де Рубрук, Марко Поло) намагалися знайти в Азії нащадків пресвітера Іоанна.
Старослов'янську варіант послання пресвітера Іоанна візантійського імператора Мануїлу - «Сказання про Індійському царстві» з'явився на Русі в XIII-XIV столітті. «Цар і поп Іван» названий на ньому «поборником по православній вірі Христовій». У «Оповіді» присутній опис фантастичних істот, очевидно, взятих з візантійського «Фізіолога».
Не виявивши царства пресвітера Іоанна в Азії, європейці з кінця XIII століття починають шукати його в Африці, де повинна була знаходитися «Третя Індія» (або «Дальня Індія»).
У 1321-1324 роках місіонер-домініканець Журден де Северак, який відвідував Африку й Азію, в творі «Опису чудес» вже ототожнював правителя Ефіопії з пресвітером Іоанном. На співвіднесення пресвітера Іоанна з царем ефіопів, ймовірно, вплинула і апокрифічна традиція. Відповідно до неї, один із старозавітних волхвів (Бальтазар) вважався чорношкірим правителем Саби і, таким чином, спадкоємцем цариці Шеви.
У XV столітті Колумб зробив свою подорож багато в чому через прагнення виявити «Велику Індію», де, за легендою, правил пресвітер Іоанн. Тоді ж прагнення знайти царство таємничого пресвітера спонукало португальського інфанта Генріха Мореплавця заохочувати своїх підданих на нові географічні відкриття.
Португальці проникають в Ефіопію і дійсно виявляють там християнська держава. Однак воно мало відповідало тій картині казкових багатств, яку малювала легенда про пресвітера Іоанна.
Пізніше, в зв'язку з погіршенням стану Ефіопії через успішних завоювань імама Ахмада аль-Газі ефіопи самі починають потребувати військової допомоги з боку португальців. Ефіопія поступово перестає ототожнюватися з землею пресвітера Іоанна.
До 1530 року відноситься остання хвиля поширення по Європі «послань пресвітера Іоанна», які, однак, не знайшли особливого відгуку. Але в європейській картографії царство пресвітера Іоанна приживається на несподівано довгий час. Аж до 17 століття нідерландські та португальські картографи приводили деталізовані карти «Абіссінії, або імперії пресвітера Іоанна», розташованої в Східній Африці. Зв'язок із легендою про пресвітера Іоанна можна знайти в самих різних творах: від роману Умберто Еко «Баудоліно» до пісень Бориса Гребенщикова і сучасних коміксів.