Si pasojë e luftës me bizantinët , nga fundi i vitit 1263, Bullgaria humbi territore të rëndësishme ndaj dy armiqve të tij kryesorë, Perandorisë Bizantine dhe Hungarisë .Konstantini mund të kërkonte vetëm ndihmë nga Tatarët e Hordhisë së Artë për t'i dhënë fund izolimit të tij.Khanët tatarë kishin qenë mbizotërues të monarkëve bullgarë për gati dy dekada, megjithëse sundimi i tyre ishte vetëm formal.Një ish-sulltan i Rumit , Kaykaus II, i cili ishte burgosur me urdhër të Mikaelit VIII, donte gjithashtu të rimarrë fronin e tij me ndihmën e tatarëve.Një nga xhaxhallarët e tij ishte një udhëheqës i shquar i Hordhisë së Artë dhe ai i dërgoi mesazhe për të bindur tatarët që të pushtonin Perandorinë Bizantine me ndihmën bullgare.Mijëra tatarë kaluan Danubin e Poshtëm të ngrirë për të pushtuar Perandorinë Bizantine në fund të vitit 1264. Konstantini shpejt u bashkua me ta, megjithëse kishte rënë nga kali dhe kishte thyer këmbën.Ushtritë e bashkuara tatare dhe bullgare filluan një sulm të papritur kundër Mikaelit VIII, i cili po kthehej nga Thesalia në Konstandinopojë, por ata nuk mundën ta kapnin perandorin.Konstantini rrethoi kështjellën bizantine të Ainos (tani Enez në Turqi), duke i detyruar mbrojtësit të dorëzoheshin.Bizantinët gjithashtu ranë dakord të lironin Kaykaus (i cili shpejt u nis për në Hordhinë e Artë), por familja e tij u mbajt e burgosur edhe më pas.