Som en konsekvens af krigen med byzantinerne mistede Bulgarien ved udgangen af ​​1263 betydelige territorier til sine to vigtigste fjender, det byzantinske rige og Ungarn .Konstantin kunne kun søge hjælp fra Tatarerne fra Den Gyldne Horde for at sætte en stopper for sin isolation.De tatariske khaner havde været de bulgarske monarkers overherrer i næsten to årtier, selvom deres styre kun var formelt.En tidligereSultan af Rum , Kaykaus II, som var blevet fængslet på Michael VIII's ordre, ønskede også at genvinde sin trone med tatarernes hjælp.En af hans onkler var en fremtrædende leder af Den Gyldne Horde, og han sendte beskeder til ham for at overtale tatarerne til at invadere det byzantinske rige med bulgarsk bistand.Tusinder af tatarer krydsede den frosne Nedre Donau for at invadere det byzantinske rige i slutningen af ​​1264. Konstantin sluttede sig hurtigt til dem, selvom han var faldet fra en hest og brækket benet.De forenede tatariske og bulgarske hære iværksatte et pludseligt angreb mod Michael VIII, der var på vej tilbage fra Thessalien til Konstantinopel, men de kunne ikke fange kejseren.Konstantin belejrede den byzantinske fæstning Ainos (nu Enez i Tyrkiet), hvilket tvang forsvarerne til at overgive sig.Byzantinerne gik også med til at løslade Kaykaus (som snart rejste til Den Gyldne Horde), men hans familie blev holdt fængslet selv derefter.