Rundt denne tiden sendte han et brev til pave Innocent III, der han oppfordret ham til å sende en utsending til Bulgaria .Han ønsket å overtale paven til å anerkjenne hans styre i Bulgaria.Innocent inngikk ivrig korrespondanse med Kaloyan fordi gjenforeningen av de kristne kirkesamfunnene under hans myndighet var et av hans hovedmål.Innocent IIIs utsending ankom Bulgaria i slutten av desember 1199, og brakte et brev fra paven til Kaloyan.Innocent uttalte at han ble informert om at Kaloyans forfedre hadde kommet "fra byen Roma".Kaloyans svar, skrevet på gammelkirkeslavisk, er ikke bevart, men innholdet kan rekonstrueres basert på hans senere korrespondanse med Den hellige stol.Kaloyan stilte seg som "keiser av bulgarerne og Vlachs", og hevdet at han var den legitime etterfølgeren til herskerne i det første bulgarske riket .Han krevde en keiserlig krone fra paven og uttrykte ønske om å sette den bulgarske ortodokse kirke under pavens jurisdiksjon.I følge Kaloyans brev til paven var Alexios III også villig til å sende en keiserlig krone til ham og til å erkjenne den bulgarske kirkens autokefale (eller autonome) status.