Around this time, he sent a letter to Pope Innocent III, urging him to dispatch an envoy to Bulgaria. He wanted to persuade the pope to acknowledge his rule in Bulgaria. Innocent eagerly entered into correspondence with Kaloyan because the reunification of the Christian denominations under his authority was one of his principal objectives.

Innocent III's envoy arrived in Bulgaria in late December 1199, bringing a letter from the Pope to Kaloyan. Innocent stated that he was informed that Kaloyan's forefathers had come "from the City of Rome". Kaloyan's answer, written in Old Church Slavonic, has not been preserved, but its content can be reconstructed based on his later correspondence with the Holy See. Kaloyan styled himself "Emperor of the Bulgarians and Vlachs", and asserted that he was the legitimate successor of the rulers of the First Bulgarian Empire. He demanded an imperial crown from the Pope and expressed his wish to put the Bulgarian Orthodox Church under the pope's jurisdiction. According to Kaloyan's letter to the Pope, Alexios III was also willing to send an imperial crown to him and to acknowledge the autocephalous (or autonomous) status of the Bulgarian Church.