Bizanslılarla yapılan savaşın bir sonucu olarak, 1263 yılının sonuna gelindiğinde Bulgaristan , iki ana düşmanı Bizans İmparatorluğu ve Macaristan'a önemli topraklarını kaptırdı.Konstantin, tecridine son vermek için yalnızca Altın Orda Tatarlarından yardım isteyebildi.Tatar hanları, yönetimleri yalnızca resmi olmasına rağmen neredeyse yirmi yıldır Bulgar hükümdarlarının derebeyleriydi.Michael VIII'in emriyle hapsedilen eskiRum Sultanı II. Kaykaus da Tatarların yardımıyla tahtını yeniden kazanmak istiyordu.Amcalarından biri Altın Orda'nın önde gelen liderlerinden biriydi ve Tatarları Bulgarların yardımıyla Bizans İmparatorluğu'nu işgal etmeye ikna etmek için ona mesajlar gönderdi.Binlerce Tatar, 1264'ün sonlarında Bizans İmparatorluğu'nu işgal etmek için donmuş Aşağı Tuna'yı geçti. Attan düşüp bacağını kırmasına rağmen Konstantin kısa süre sonra onlara katıldı.Birleşik Tatar ve Bulgar orduları, Tesalya'dan Konstantinopolis'e dönen VIII. Michael'a ani bir saldırı başlattı ancak imparatoru yakalayamadılar.Konstantin, Bizans kalesi Ainos'u (şimdi Türkiye'de Enez) kuşatarak savunucuları teslim olmaya zorladı.Bizanslılar da (kısa süre sonra Altın Orda'ya gitmek üzere ayrılan) Kaykaus'u serbest bırakmayı kabul etti, ancak ailesi daha sonra bile hapiste tutuldu.