Rostislav Mihajlovič napao je Bugarsku uz mađarsku pomoć 1259. Sljedeće godine Rostislav je napustio svoje vojvodstvo da bi se pridružio pohodu svog tasta, Béle IV od Mađarske, protiv Češke.Iskoristivši Rostislavovu odsutnost, Konstantin je provalio u njegovo kraljevstvo i ponovno zauzeo Vidin.Poslao je i vojsku u napad na Severinsku banovinu, ali je mađarski zapovjednik Lovro odbio osvajače.Bugarska invazija na Severin razbjesnila je Bélu IV.Ubrzo nakon što je u ožujku 1261. sklopio mirovni sporazum s Otokarom II od Češke, mađarske su trupe upale u Bugarsku pod zapovjedništvom sina i nasljednika Béle IV., Stjepana.Zauzeli su Vidin i opsjeli Lom na Donjem Dunavu, ali nisu uspjeli dovesti Konstantina u oštru bitku, jer se on povukao u Trnovo.Mađarska vojska napustila je Bugarsku prije kraja godine, ali je pohod vratio sjeverozapadnu Bugarsku Rostislavu.