Der Priester Johannes ist eine Gestalt, von der keiner so recht weiß, ob sie wirklich lebt oder erfunden ist. Otto von Freising ist es, der zum erstenmal von diesem Priester gehört hat.

… ich habe geschrieben, daß vor geraumer Zeit, als Eugen III. auf dem Stuhl Petri saß, der syrische Bischof Hugo von Gabala, der mit einer armenischen Gesandtschaft zu Besuch beim Papst war, ihm erzählte, es gebe im äußersten fernen Osten, in der Nähe des Irdischen Paradieses, das Reich eines Priesterkönigs, des sogenannten Presbyter Johannes, der sicher ein christlicher König sei, wenn auch ein Anhänger der Nestorianischen Häresie, und dessen Vorfahren jene Magier aus dem Morgenlande gewesen seien, Priesterkönige auch sie, aber Inhaber einer uralten Weisheit, die das Jesuskind in der Krippe besucht hatten."
"Und was habe ich, der Kaiser des Heiligen Römischen Reiches, mit diesem Priester Johannes zu tun, den der Herr noch lange als Priesterkönig bewahren möge in seinem Maurenreich, wo immer das liegen mag?"
"Siehst du, mein illustrer Neffe, der du Mauren sagst und dabei genauso denkst wie die anderen christlichen Könige, die sich in der Verteidigung Jerusalems verausgaben - eine überaus fromme Unternehmung, kein Zweifel, aber überlaß sie dem König von Frankreich, nachdem jetzt ohnehin die Franken in Jerusalem das große Wort führen. Die Bestimmung der Christenheit und eines jeden Reiches, das sich als heilig und römisch versteht, liegt jenseits der Mauren. Es gibt ein christliches Reich im Osten von Jerusalem und dem Lande der Ungläubigen. Und der Kaiser, dem es gelänge, die beiden Reiche zu vereinigen, würde dadurch das Reich der Ungläubigen und selbst das von Byzanz auf zwei einsame Inseln reduzieren, die verloren im großen Meer seines Ruhmes lägen!"
"Phantasien, lieber Onkel. Bleiben wir mit den Beinen auf dem Boden, wenn's recht ist."

Weder ihm noch Baudolino wird es gelingen, Friedrich Barbarossa zu einer Reise in das sagenhafte Land zu bewegen. Und das grenzt schon fast an ein Wunder, denn Baudolinos Bemühungen sind beachtlich: Gemeinsam mit seinen Studienfreunden erdichtet er einen Brief des Priesters Johannes an Friedrich Barbarossa, der dann tatsächlich, Jahre später, auftaucht. Allerdings ist dieser Brief an einen gewissen Basileus Manuel gerichtet. Und Papst Alexander III. ist sich nicht zu schade, sogar einen Antwortbrief zu verfassen. So geht es hin und her und nach Friedrich Barbarossas plötzlichem Tod, macht sich eine seltsame Gruppe endlich auf zur Reise in das unbekannte Land.

Während also jeder jedem mißtraute, mußten unsere Freunde entscheiden, wer an der Reise teilnehmen sollte. Der Poet hatte zu bedenken gegeben, daß sie zwölf sein müßten. Denn wenn sie während der Reise zum Land des Priesters Johannes respektvoll behandelt werden wollten, sei es ratsam, die Leute glauben zu lassen, sie seien die zwölf Magierkönige auf dem Rückweg aus Bethlehem. Da jedoch nicht gesichert sei, ob die Magier wirklich zwölf waren oder doch nur drei, dürfe keiner von ihnen jemals sagen, daß sie die Magier seien; im Gegenteil, wenn jemand sie fragte, müßten sie es verneinen, aber so, daß es klinge, als hätten sie ein großes Geheimnis zu wahren. Gerade wenn und weil sie es gegenüber allen verneinten, würde es jeder glauben, der es glauben wolle. Der Glaube der anderen würde aus ihrer Zurückhaltung eine Bejahung machen.
Nun waren da Baudolino, der Poet, Boron, Kyot, Abdul Solomon und Boidi. Zosimos war unverzichtbar, da er fortfuhr zu schwören, er habe die Karte des Kosmas Indikopleustes im Kopf, auch wenn es allen nicht wenig gegen den Strich ging, daß dieser Widerling einen der Magier darstellen sollte, aber man durfte nicht zimperlich sein. Es fehlten also noch vier Personen. Baudolino traute inzwischen nur noch den Alexandrinern, und so weihte er vier von ihnen in das Vorhaben ein: den Cuttica aus Quargnento, seinen Schwager Colandrino Guasco, den Porcello und den Aleramo Scaccabarozzi, genannt il Ciula, der trotz seines Spitznamens ("der Dödel") ein solider und zuverlässiger Mann war, der nicht viele Fragen stellte. Sie erklärten sich einverstanden, da auch ihnen inzwischen schien, daß es mit Jerusalem ohnehin nichts mehr werden würde. Der junge Friedrich gab ihnen zwölf Pferde und sieben Maultiere mit Verpflegung für eine Woche. Danach, sagte er, werde sich die Göttliche Vorsehung um sie kümmern.