A bizánci háború következtében 1263 végére Bulgária jelentős területeket veszített két legfőbb ellenségének, a Bizánci Birodalomnak és Magyarországnak .Konstantin csak az Arany Horda tatárjaitól kérhetett segítséget, hogy véget vessen elszigeteltségének.A tatár kánok csaknem két évtizeden át voltak a bolgár uralkodók urai, bár uralmuk csak formális volt.Rum egykori szultánja , II. Kaykaus, akit VIII. Mihály parancsára bebörtönöztek, szintén a tatárok segítségével akarta visszaszerezni trónját.Egyik nagybátyja az Arany Horda kiemelkedő vezetője volt, és üzeneteket küldött neki, hogy rávegye a tatárokat a Bizánci Birodalom megszállására bolgár segítséggel.Tatárok ezrei keltek át a befagyott Al-Dunán, hogy 1264 végén betörjenek a Bizánci Birodalomba. Konstantin hamarosan csatlakozott hozzájuk, bár leesett lóról és eltörte a lábát.Az egyesült tatár és bolgár hadsereg hirtelen támadást indított a Thesszáliából Konstantinápolyba visszatérő VIII. Mihály ellen, de a császárt nem tudták elfogni.Konstantin ostrom alá vette Ainos bizánci erődjét (ma Enez Törökországban), és megadásra kényszerítette a védőket.A bizánciak abba is beleegyeztek, hogy Kaykaust (aki hamarosan az Arany Hordába távozott) elengedjék, de a családját ezután is börtönben tartották.