As a consequence of the war with the Byzantines, by the end of 1263, Bulgaria lost significant territories to his two principal enemies, the Byzantine Empire and Hungary. Konstantin could only seek assistance from the Tatars of the Golden Horde to put an end to his isolation. The Tatar khans had been the overlords of the Bulgarian monarchs for almost two decades, although their rule was only formal. A former Sultan of Rum, Kaykaus II, who had been imprisoned at Michael VIII's order, also wanted to regain his throne with the Tatars' help. One of his uncles was a prominent leader of the Golden Horde and he sent messages to him to persuade the Tatars to invade the Byzantine Empire with Bulgarian assistance.

Thousands of Tatars crossed the frozen Lower Danube to invade the Byzantine Empire in late 1264. Konstantin soon joined them, although he had fallen from a horse and broken his leg. The united Tatar and Bulgarian armies launched a sudden attack against Michael VIII who was returning from Thessaly to Constantinople, but they could not capture the emperor. Konstantin laid siege the Byzantine fortress of Ainos (now Enez in Turkey), forcing the defenders to surrender. The Byzantines also agreed to release Kaykaus (who soon left for the Golden Horde), but his family was kept imprisoned even thereafter.