Ως συνέπεια του πολέμου με τους Βυζαντινούς , στα τέλη του 1263, η Βουλγαρία έχασε σημαντικά εδάφη από τους δύο κύριους εχθρούς της, τη Βυζαντινή Αυτοκρατορία και την Ουγγαρία .Ο Κωνσταντίνος δεν μπορούσε παρά να ζητήσει βοήθεια από τους Τατάρους της Χρυσής Ορδής για να βάλει τέλος στην απομόνωσή του.Οι Τάταροι χάνοι ήταν οι άρχοντες των Βούλγαρων μοναρχών για σχεδόν δύο δεκαετίες, αν και η κυριαρχία τους ήταν μόνο τυπική.Ένας πρώηνσουλτάνος ​​του Ρουμ , ο Kaykaus II, που είχε φυλακιστεί με εντολή του Μιχαήλ Η', ήθελε επίσης να ανακτήσει τον θρόνο του με τη βοήθεια των Τατάρων.Ένας από τους θείους του ήταν εξέχων αρχηγός της Χρυσής Ορδής και του έστειλε μηνύματα να πείσει τους Τατάρους να εισβάλουν στη Βυζαντινή Αυτοκρατορία με τη Βουλγαρική βοήθεια.Χιλιάδες Τάταροι διέσχισαν τον παγωμένο Κάτω Δούναβη για να εισβάλουν στη Βυζαντινή Αυτοκρατορία στα τέλη του 1264. Ο Κωνσταντίνος σύντομα ενώθηκε μαζί τους, αν και είχε πέσει από ένα άλογο και είχε σπάσει το πόδι του.Οι ενωμένοι Ταταρικοί και Βουλγαρικοί στρατοί εξαπέλυσαν αιφνίδια επίθεση κατά του Μιχαήλ Η' που επέστρεφε από τη Θεσσαλία στην Κωνσταντινούπολη, αλλά δεν μπόρεσαν να συλλάβουν τον αυτοκράτορα.Ο Κωνσταντίνος πολιόρκησε το βυζαντινό φρούριο του Αίνου (τώρα Ένεζ στην Τουρκία), αναγκάζοντας τους υπερασπιστές να παραδοθούν.Οι Βυζαντινοί συμφώνησαν επίσης να απελευθερώσουν τον Kaykaus (που σύντομα έφυγε για τη Χρυσή Ορδή), αλλά η οικογένειά του κρατήθηκε φυλακισμένη ακόμη και μετά.