Ungefähr zu dieser Zeit sandte er einen Brief an Papst Innozenz III. und forderte ihn auf, einen Gesandten nach Bulgarien zu entsenden.Er wollte den Papst davon überzeugen, seine Herrschaft in Bulgarien anzuerkennen.Innocent nahm eifrig den Briefwechsel mit Kaloyan auf, da die Wiedervereinigung der christlichen Konfessionen unter seiner Autorität eines seiner Hauptziele war.Der Gesandte von Innozenz III. traf Ende Dezember 1199 in Bulgarien ein und überbrachte Kaloyan einen Brief des Papstes.Innocent gab an, er sei darüber informiert worden, dass Kaloyans Vorfahren „aus der Stadt Rom“ gekommen seien.Kalojans in altkirchenslawischer Sprache verfasste Antwort ist nicht erhalten, ihr Inhalt lässt sich jedoch anhand seiner späteren Korrespondenz mit dem Heiligen Stuhl rekonstruieren.Kaloyan bezeichnete sich selbst als „Kaiser der Bulgaren und Walachen“ und behauptete, er sei der legitime Nachfolger der Herrscher des Ersten Bulgarischen Reiches .Er forderte vom Papst eine Kaiserkrone und äußerte den Wunsch, die bulgarisch-orthodoxe Kirche der Gerichtsbarkeit des Papstes zu unterstellen.Laut Kalojans Brief an den Papst war Alexios III. auch bereit, ihm eine Kaiserkrone zu schicken und den autokephalen (oder autonomen) Status der bulgarischen Kirche anzuerkennen.