לפי לאודווין, הבישוף הידוע הראשון של ביהאר, סטיבן התחבר לאימפריה הביזנטית והוביל משלחת צבאית לסייע להם נגד "ברברים" בחצי האי הבלקני.הכוחות הביזנטים וההונגרים לקחו ביחד "Cesaries" שגיורפי מזהה כעיר אוכריד של ימינו.הדיווח של לאודווין מעלה שסטיבן הצטרף לביזאנטים במלחמה שהסתיימה עם כיבוש בולגריה בשנת 1018. עם זאת, התאריך המדויק של המשלחת שלו אינו ברור.גיורפי טוען שרק בשנה האחרונה של המלחמה הוביל סטיבן את חייליו נגד הבולגרים.כיבוש זה סיים את האימפריה הבולגרית הראשונה .