Charles I of Anjou and Baldwin II, the dispossessed Latin emperor of Constantinople, made an alliance against the Byzantine Empire in 1267. To prevent Bulgaria from joining the anti-Byzantine coalition, Michael VIII offered his niece, Maria Palaiologina Kantakouzene, to the widowed Konstantin in 1268. The emperor also pledged that he would return Mesembria and Anchialos to Bulgaria as her dowry if she gave birth to a son. Konstantin married Maria, but Michael VIII broke his promise and did not renounce the two towns after the birth of Konstantin and Maria's son, Michael. Outraged by the emperor's betrayal, Konstantin sent envoys to Charles to Naples in September 1271. The negotiations continued during the following years, showing that Konstantin was willing to support Charles against the Byzantines.

Konstantin broke into Thrace in 1271 or 1272, but Michael VIII persuaded Nogai, the dominant figure in the westernmost territory of the Golden Horde, to invade Bulgaria. The Tatars plundered the country, forcing Konstantin to return and abandon his claim to the two towns. Nogai set up his capital in Isaccea near the Danube Delta, thus he could easily attack Bulgaria. Konstantin had been seriously injured after a riding accident and could not move without assistance, because he was paralyzed from the waist down. The paralyzed Konstantin could not prevent Nogai's Tatars from making regular plundering raids against Bulgaria.