Bysanttilaisten kanssa käydyn sodan seurauksena Bulgaria menetti vuoden 1263 loppuun mennessä merkittäviä alueita kahdelle pääviholliselleen, Bysantin valtakunnalle ja Unkarille .Konstantin saattoi vain pyytää apua Kultahorden tataareilta tehdäkseen lopun eristyneisyydestään.Tataarikhaanit olivat olleet Bulgarian monarkkien yliherroja lähes kahden vuosikymmenen ajan, vaikka heidän hallintonsa oli vain muodollista.Myös entinenRumin sulttaani Kaykaus II, joka oli vangittu Mikael VIII:n käskystä, halusi saada takaisin valtaistuimensa tataarien avulla.Yksi hänen sedoistaan ​​oli merkittävä Kultahorden johtaja ja hän lähetti hänelle viestejä taivutellakseen tataareita hyökkäämään Bysantin valtakuntaan Bulgarian avustuksella.Tuhannet tataarit ylittivät jäätyneen Ala-Tonavan hyökätäkseen Bysantin valtakuntaan vuoden 1264 lopulla. Pian Konstantin liittyi heihin, vaikka hän oli pudonnut hevoselta ja murtanut jalkansa.Tatarien ja Bulgarian yhdistyneet armeijat aloittivat äkillisen hyökkäyksen Michael VIII:aa vastaan, joka oli palaamassa Tessaliasta Konstantinopoliin, mutta he eivät kyenneet vangitsemaan keisaria.Konstantin piiritti bysanttilaista Ainosin linnoitusta (nykyinen Enez Turkissa) ja pakotti puolustajat antautumaan.Bysanttilaiset suostuivat myös vapauttamaan Kaykauden (joka lähti pian Kultahordelle), mutta hänen perheensä pidettiin vangittuna senkin jälkeen.