Konstantin's minor brother-in-law, John IV Laskaris, was dethroned and blinded by his former guardian and co-ruler, Michael VIII Palaiologos, before the end of 1261. Michael VIII's army had occupied Constantinople already in July, thus the coup made him the sole ruler of the restored Byzantine Empire. The rebirth of the empire changed the traditional relations between the powers of the Balkan Peninsula. Furthermore, Konstantine's wife decided to take vengeance of her brother's mutilation and persuaded Konstantine to turn against Michael.

Mitso Asen, former emperor, who still held southeastern Bulgaria, made an alliance with the Byzantines, but another powerful nobleman, Jacob Svetoslav, who had taken control of the southwestern region, was loyal to Konstantine. Benefiting from a war between the Byzantine Empire, the Republic of Venice, Achaea and Epirus, Konstantine invaded Thrace and captured Stanimaka and Philippopolis in the autumn of 1262. Mitso was also forced to flee to Mesembria (now Nesebar in Bulgaria). After Konstantine laid siege to the town, Mitso sought assistance from the Byzantines, offering to surrender Mesembria to them in exchange for landed property in the Byzantine Empire. Michael VIII accepted the offer and sent Michael Glabas Tarchaneiotes to help Mitso in 1263.

A second Byzantine army stormed into Thrace and recaptured Stanimaka and Philippopolis. After seizing Mesembria from Mitso, Glabas Tarchaneiotes continued his campaign along the Black Sea and occupied Agathopolis, Sozopolis and Anchialos. Meanwhile, the Byzantine fleet took control of Vicina and other ports at the Danube Delta. Glabas Tarchaneiotes attacked Jacob Svetoslav who could only resist with Hungarian assistance, thus he accepted Béla IV's suzerainty.