Leodvinin, ensimmäisen tunnetun Biharin piispan, mukaan Stephen liittoutui Bysantin valtakunnan kanssa ja johti sotilasretkikuntaa auttaakseen heitä "barbaareja" vastaan ​​Balkanin niemimaalla.Bysantin ja Unkarin joukot valtasivat yhdessä "Cesariesin", jonka Györffy tunnistaa nykyiseksi Ohridin kaupungiksi.Leodvinin raportti viittaa siihen, että Stephen liittyi bysanttilaisten joukkoon sotaan, joka päättyi heidän valloitukseensa Bulgarian vuonna 1018. Hänen tutkimusmatkansa tarkka päivämäärä on kuitenkin epävarma.Györffy väittää, että Stephen johti joukkonsa bulgarialaisia ​​vastaan ​​vasta sodan viimeisenä vuonna.Tämä valloitus päätti ensimmäisen Bulgarian valtakunnan .