В резултат на войната с византийците , до края на 1263 г., България губи значителни територии от двамата си основни врагове, Византийската империя и Унгария .Константин можеше само да потърси помощ от татарите от Златната орда, за да сложи край на своята изолация.Татарските ханове са били господари на българските монарси почти две десетилетия, въпреки че управлението им е било само формално.Бившиятсултан на Рум , Кайкаус II, който е бил затворен по заповед на Михаил VIII, също иска да си върне трона с помощта на татарите.Един от чичовците му е виден водач на Златната орда и той му изпраща послания да убеди татарите да нападнат Византийската империя с българска помощ.Хиляди татари прекосяват замръзналия Долен Дунав, за да нападнат Византийската империя в края на 1264 г. Константин скоро се присъединява към тях, въпреки че е паднал от кон и е счупил крака си.Обединените татарски и български войски предприемат внезапна атака срещу Михаил VIII, който се връща от Тесалия към Константинопол, но не успяват да заловят императора.Константин обсажда византийската крепост Айнос (сега Енез в Турция), принуждавайки защитниците да се предадат.Византийците също се съгласяват да освободят Кайкаус (който скоро заминава за Златната орда), но семейството му е държано в затвора дори след това.