Volgens Leodvin, de eerste bekende bisschop van Bihar, sloot Stefanus zich aan bij het Byzantijnse rijk en leidde hij een militaire expeditie om hen te helpen tegen "barbaren" op het Balkanschiereiland.De Byzantijnse en Hongaarse troepen namen gezamenlijk "Cesaries" in, dat Györffy identificeert als de huidige stad Ohrid.Leodvins rapport suggereert dat Stefanus zich bij de Byzantijnen voegde in de oorlog die eindigde met hun verovering van Bulgarije in 1018. De exacte datum van zijn expeditie is echter onzeker.Györffy stelt dat Stephen pas in het laatste jaar van de oorlog zijn troepen tegen de Bulgaren leidde.Deze verovering maakte een einde aan het Eerste Bulgaarse Rijk .