Konstantins mindre svoger, John IV Laskaris, blev detroniseret og blindet af sin tidligere værge og medhersker, Michael VIII Palaiologos , inden udgangen af ​​1261. Michael VIII's hær havde besat Konstantinopel allerede i juli, og kuppet gjorde ham således enehersker over det genoprettede byzantinske rige.Imperiets genfødsel ændrede de traditionelle forhold mellem Balkanhalvøens magter.Desuden besluttede Konstantines kone at tage hævn over sin brors lemlæstelse og overtalte Konstantin til at vende sig mod Michael.Mitso Asen, tidligere kejser, som stadig holdt det sydøstlige Bulgarien , sluttede en alliance med byzantinerne, men en anden magtfuld adelsmand, Jacob Svetoslav, som havde taget kontrol over den sydvestlige region, var loyal over for Konstantin.Konstantin dragede fordel af en krig mellem det byzantinske rige, Republikken Venedig , Achaea og Epirus, invaderede Thrakien og erobrede Stanimaka og Philippopolis i efteråret 1262. Mitso blev også tvunget til at flygte til Mesembrien (nu Nesebar i Bulgarien).Efter at Konstantine havde belejret byen, søgte Mitso bistand fra byzantinerne og tilbød at overgive Mesembria til dem i bytte for jordejendom i det byzantinske imperium.Michael VIII accepterede tilbuddet og sendte Michael Glabas Tarchaneiotes for at hjælpe Mitso i 1263.En anden byzantinsk hær stormede ind i Thrakien og generobrede Stanimaka og Philippopolis.Efter at have erobret Mesembria fra Mitso, fortsatte Glabas Tarchaneiotes sit felttog langs Sortehavet og besatte Agathopolis, Sozopolis og Anchialos.I mellemtiden tog den byzantinske flåde kontrol over Vicina og andre havne ved Donau-deltaet.Glabas Tarchaneiotes angreb Jacob Svetoslav, der kun kunne gøre modstand med ungarsk bistand, og dermed accepterede han Béla IV's overherredømme.