Ca o consecință a războiului cu bizantinii , până la sfârșitul anului 1263, Bulgaria a pierdut teritorii semnificative în fața celor doi principali dușmani ai săi, Imperiul Bizantin și Ungaria .Konstantin nu putea decât să ceară ajutor de la tătarii Hoardei de Aur pentru a pune capăt izolării sale.Hanii tătari au fost stăpânii monarhilor bulgari de aproape două decenii, deși domnia lor era doar formală.Un fostsultan de Rum , Kaykaus al II-lea, care fusese închis la ordinul lui Mihai al VIII-lea, a vrut și el să-și recapete tronul cu ajutorul tătarilor.Unul dintre unchii săi a fost un lider proeminent al Hoardei de Aur și i-a trimis mesaje pentru a-i convinge pe tătari să invadeze Imperiul Bizantin cu asistență bulgară.Mii de tătari au traversat Dunărea de Jos înghețată pentru a invada Imperiul Bizantin la sfârșitul anului 1264. Konstantin li sa alăturat curând, deși căzuse de pe cal și și-a rupt piciorul.Armatele tătare și bulgare unite au lansat un atac brusc împotriva lui Mihai al VIII-lea care se întorcea din Tesalia la Constantinopol, dar nu l-au putut captura pe împărat.Konstantin a asediat fortăreața bizantină Ainos (acum Enez în Turcia), forțând apărătorii să se predea.Bizantinii au fost, de asemenea, de acord să-l elibereze pe Kaykaus (care a plecat curând în Hoarda de Aur), dar familia sa a fost ținută în închisoare chiar și după aceea.