Otprilike u to vrijeme poslao je pismo papi Inocentu III., pozivajući ga da pošalje izaslanika u Bugarsku .Htio je papu nagovoriti da prizna njegovu vlast u Bugarskoj.Inocent je gorljivo stupio u korespondenciju s Kaloyanom jer je ponovno ujedinjenje kršćanskih denominacija pod njegovom vlašću bio jedan od njegovih glavnih ciljeva.Izaslanik Inocenta III stigao je u Bugarsku krajem prosinca 1199., donoseći papino pismo Kaloyanu.Inocent je izjavio da je obaviješten da su Kaloyanovi preci došli "iz grada Rima".Kalojanov odgovor, napisan na staroslavenskom, nije sačuvan, ali se njegov sadržaj može rekonstruirati na temelju njegove kasnije korespondencije sa Svetom Stolicom.Kalojan se nazivao "carem Bugara i Vlaha" i tvrdio da je legitimni nasljednik vladara Prvog bugarskog carstva .Zatražio je od pape carsku krunu i izrazio želju da Bugarsku pravoslavnu crkvu stavi pod papinu jurisdikciju.Prema Kalojanovom pismu papi, Aleksije III je također bio voljan poslati mu carsku krunu i priznati autokefalni (ili autonomni) status Bugarske crkve.