Rreth kësaj kohe, ai i dërgoi një letër Papa Inocentit III, duke i kërkuar atij të dërgonte një të dërguar në Bullgari .Ai donte të bindte papën të pranonte sundimin e tij në Bullgari.Innocenti hyri me padurim në korrespondencë me Kaloyan sepse ribashkimi i besimeve të krishtera nën autoritetin e tij ishte një nga objektivat e tij kryesore.I dërguari i Inocent III mbërriti në Bullgari në fund të dhjetorit 1199, duke i sjellë një letër nga Papa Kaloyan.Innocent deklaroi se ishte informuar se paraardhësit e Kaloyan kishin ardhur "nga qyteti i Romës".Përgjigja e Kaloyan, e shkruar në sllavishten e vjetër kishtare, nuk është ruajtur, por përmbajtja e saj mund të rindërtohet bazuar në korrespondencën e tij të mëvonshme me Selinë e Shenjtë.Kaloyan e quajti veten "Perandor i bullgarëve dhe vllehëve" dhe pohoi se ai ishte pasardhësi legjitim i sundimtarëve të Perandorisë së Parë Bullgare .Ai kërkoi një kurorë perandorake nga Papa dhe shprehu dëshirën e tij për të vënë Kishën Ortodokse Bullgare nën juridiksionin e Papës.Sipas letrës së Kaloyan drejtuar Papës, Aleksi III ishte gjithashtu i gatshëm t'i dërgonte një kurorë perandorake dhe të njihte statusin autoqefal (ose autonome) të Kishës Bullgare.