According to Leodvin, the first known Bishop of Bihar, Stephen allied with the Byzantine Empire and led a military expedition to assist them against "barbarians" in the Balkan Peninsula. The Byzantine and Hungarian troops jointly took "Cesaries" which Györffy identifies as the present-day town of Ohrid. Leodvin's report suggests that Stephen joined the Byzantines in the war ending with their conquest of Bulgaria in 1018. However, the exact date of his expedition is uncertain. Györffy argues that it was only in the last year of the war that Stephen led his troops against the Bulgarians.

This conquest ended the First Bulgarian Empire.