Do hậu quả của cuộc chiến với người Byzantine , vào cuối năm 1263, Bulgaria đã mất những vùng lãnh thổ quan trọng vào tay hai kẻ thù chính của mình là Đế quốc Byzantine và Hungary .Konstantin chỉ có thể tìm kiếm sự trợ giúp từ người Tatar của Golden Horde để chấm dứt tình trạng cô lập của mình.Các hãn Tatar đã là lãnh chúa của các quốc vương Bulgaria trong gần hai thập kỷ, mặc dù sự cai trị của họ chỉ mang tính hình thức.CựuSultan của Rum , Kaykaus II, người từng bị giam cầm theo lệnh của Michael VIII, cũng muốn giành lại ngai vàng của mình với sự giúp đỡ của người Tatar.Một trong những người chú của ông là một thủ lĩnh nổi tiếng của Golden Horde và ông đã gửi tin nhắn cho ông ta để thuyết phục người Tatars xâm lược Đế quốc Byzantine với sự hỗ trợ của người Bulgaria.Hàng nghìn người Tatars đã vượt qua vùng Hạ Danube băng giá để xâm chiếm Đế quốc Byzantine vào cuối năm 1264. Konstantin nhanh chóng gia nhập cùng họ, mặc dù anh ta đã bị ngã ngựa và gãy chân.Quân đội thống nhất của Tatar và Bulgaria đã phát động một cuộc tấn công bất ngờ chống lại Michael VIII đang trở về từ Thessaly đến Constantinople, nhưng họ không thể bắt được hoàng đế.Konstantin đã bao vây pháo đài Ainos của Byzantine (nay là Enez ở Thổ Nhĩ Kỳ), buộc quân phòng thủ phải đầu hàng.Người Byzantine cũng đồng ý thả Kaykaus (người đã sớm rời đến Golden Horde), nhưng gia đình anh ta vẫn bị giam giữ ngay cả sau đó.