Као последица рата са Византинцима , до краја 1263. Бугарска је изгубила значајне територије од своја два главна непријатеља, Византијског царства и Угарске .Константин је могао само да тражи помоћ од Татара Златне Хорде да оконча своју изолацију.Татарски канови су скоро две деценије били господари бугарских монарха, иако је њихова власт била само формална.Бившисултан Рума Кајкаус ИИ, који је био затворен по наређењу Михаила ВИИИ, такође је желео да поврати свој престо уз помоћ Татара.Један од његових ујака био је истакнути вођа Златне Хорде и слао му је поруке да убеди Татаре да уз бугарску помоћ упадну у Византијско царство.Хиљаде Татара прешло је залеђени Доњи Дунав у инвазију на Византијско царство крајем 1264. Константин им се убрзо придружио, иако је пао са коња и сломио ногу.Уједињене татарске и бугарске војске су изненадно напале Михаила ВИИИ који се враћао из Тесалије у Цариград, али нису успеле да заробе цара.Константин је опседао византијску тврђаву Аинос (данас Енез у Турској), приморавши браниоце да се предају.Византинци су такође пристали да ослободе Кајкауса (који је убрзо отишао у Златну Хорду), али је његова породица и након тога остала у затвору.