Konstantin kiskorú sógorát, IV. Laskaris Jánost korábbi gyámja és társuralkodója, VIII. Mihály Palaiologosz 1261 vége előtt letaszította és megvakította. VIII. Mihály hadserege már júliusban elfoglalta Konstantinápolyt, így a puccs tette őt. a helyreállított Bizánci Birodalom egyedüli uralkodója.A birodalom újjászületése megváltoztatta a Balkán-félsziget hatalmai közötti hagyományos kapcsolatokat.Továbbá Konstantine felesége úgy döntött, hogy bosszút áll bátyja megcsonkításáért, és rávette Konstantine-t, hogy forduljon Michael ellen.Mitso Asen, az egykori császár, aki továbbra is birtokolta Bulgária délkeleti részét, szövetséget kötött a bizánciakkal, de egy másik hatalmas nemes, Jacob Svetoslav, aki átvette az irányítást a délnyugati régió felett, hűséges volt Konsztantyinhoz.A Bizánci Birodalom, a Velencei Köztársaság , Akhaia és Epirusz közötti háború hasznát húzva Konstantinus megtámadta Trákiát, és elfoglalta Stanimakát és Philippopolist 1262 őszén. Mitso is kénytelen volt Mesembriába (ma, Neszebar Bulgáriában) menekülni.Miután Konstantine ostrom alá vette a várost, Mitso segítséget kért a bizánciaktól, és felajánlotta nekik, hogy a Bizánci Birodalom birtokáért cserébe átadja nekik Mesembriát.VIII. Mihály elfogadta az ajánlatot, és 1263-ban elküldte Michael Glabas Tarchaneiotest Mitso segítségére.A második bizánci hadsereg berontott Trákiába, és visszafoglalta Stanimakát és Philippopolist.Miután elfoglalta Mesembriát Mitsotól, Glabas Tarchaneiotes folytatta hadjáratát a Fekete-tenger mentén, és elfoglalta Agathopolist, Sozopolist és Anchialost.Eközben a bizánci flotta átvette Vicinát és a Duna-delta más kikötőit.Glabas Tarchaneiotes megtámadta Jacob Svetoslavot, aki csak magyar segítséggel tudott ellenállni, így elfogadta IV. Béla szuzerenitását.