In questo periodo inviò una lettera a papa Innocenzo III, esortandolo a inviare un inviato in Bulgaria .Voleva persuadere il papa a riconoscere il suo governo in Bulgaria.Innocent entrò con entusiasmo in corrispondenza con Kaloyan perché la riunificazione delle denominazioni cristiane sotto la sua autorità era uno dei suoi obiettivi principali.L'inviato di Innocenzo III arrivò in Bulgaria alla fine di dicembre 1199, portando una lettera del Papa a Kaloyan.Innocent ha dichiarato di essere stato informato che gli antenati di Kaloyan provenivano "dalla città di Roma".La risposta di Kaloyan, scritta in antico slavo ecclesiastico, non è stata conservata, ma il suo contenuto può essere ricostruito sulla base della sua successiva corrispondenza con la Santa Sede.Kaloyan si definì "Imperatore dei Bulgari e dei Valacchi" e affermò di essere il legittimo successore dei sovrani del Primo Impero bulgaro .Ha chiesto una corona imperiale al Papa e ha espresso il desiderio di mettere la Chiesa ortodossa bulgara sotto la giurisdizione del papa.Secondo la lettera di Kaloyan al Papa, Alessio III era disposto anche a inviargli una corona imperiale e a riconoscere lo status autocefalo (o autonomo) della Chiesa bulgara.