Come conseguenza della guerra con i Bizantini , alla fine del 1263, la Bulgaria perse territori significativi a favore dei suoi due principali nemici, l'Impero bizantino e l'Ungheria .Konstantin poteva solo chiedere aiuto ai Tartari dell'Orda d'Oro per porre fine al suo isolamento.I khan tartari erano stati i signori dei monarchi bulgari per quasi due decenni, sebbene il loro governo fosse solo formale.Anche un exsultano di Rum , Kaykaus II, che era stato imprigionato per ordine di Michele VIII, voleva riconquistare il suo trono con l'aiuto dei tartari.Uno dei suoi zii era un leader di spicco dell'Orda d'Oro e gli inviò messaggi per persuadere i tartari a invadere l'impero bizantino con l'assistenza bulgara.Migliaia di tartari attraversarono il basso Danubio ghiacciato per invadere l'impero bizantino alla fine del 1264. Konstantin si unì presto a loro, sebbene fosse caduto da cavallo e si fosse rotto una gamba.Gli eserciti uniti tartari e bulgari lanciarono un attacco improvviso contro Michele VIII che stava tornando dalla Tessaglia a Costantinopoli, ma non riuscirono a catturare l'imperatore.Costantino assediò la fortezza bizantina di Ainos (ora Enez in Turchia), costringendo i difensori alla resa.I bizantini accettarono anche di liberare Kaykaus (che presto partì per l'Orda d'Oro), ma la sua famiglia fu tenuta imprigionata anche da allora in poi.