האראלד השלישי, מלך נורווגיה
הגלות במזרח > בשירות האימפריה הביזנטית

לאחר כמה שנים ברוס של קייב, עברו האראלד והכוח שתחת פיקודו שמנה כ-500 איש דרומה לקונסטנטינופול, בירתה של האימפריה הביזנטית, ככל הנראה בשנת 1033 או 1034, שם הם הצטרפו למשמר הורנגים. למרות ש"ספר האי השטוח" (Flateyjarbók) טוען שבתחילה העדיף האראלד לשמור על זהותו המלכותית בסוד, רוב המקורות מסכימים שהמוניטין שלו ושל אנשיו היה ידוע היטב במזרח באותה תקופה. בעוד שמשמר הוורנגים היה מיועד בעיקר לתפקד כמשמר שומרי הראש של הקיסר, מצא עצמו האראלד בפעילות קרבית בכל רחבי האימפריה. פעולתו הקרבית הראשונה במסגרת זו הייתה כנגד שודדי ים ערבים בים התיכון ולאחר מכן בערים בתוככי אסיה הקטנה שהעניקו סיוע לשודדי הים. באותה התקופה, על פי סנורי סטורלוסון, הוא הפך ל"מנהיגם של כל הורנגים". ב-1035 דחקו הביזנטים את הערבים מחוץ לאסיה הקטנה והאראלד לקח חלק במערכות הצבאיות שהתקדמו עד לנהר הפרת, שם על פי משורר החצר שלו, תיודולף ארנורסון, הוא השתתף בכיבושם של שמונים מבצרים ערביים, מספר שההיסטוריונים זיגיפוס בלונדל ובנדיקט בנדיקז לא רואים כל סיבה לפקפק בנכונותו. למרות שהוא לא היה מפקד עצמאי בשום צבא כפי שנרמז בסאגות, לא נראה סביר שהאראלד והורנגים לא נשלחו באותה תקופה למשימת כיבוש עיר או מצודה. במהלך ארבע השנים הראשונות למלכותו של מיכאל הרביעי פפלגוניאן, קיסר האימפריה הביזנטית, השתתף האראלד ככל הנראה במערכות כנגד הפצ'נגים.
לאחר מכן, על פי המדווח בסאגות, יצא האראלד לירושלים ולחם בקרבות באזור. למרות שהסאגות מתארות את פעולותיו אלו בסדר כרונולוגי לאחר מסעו לסיציליה, מפקפק ההיסטוריון קלי דה-ווירס בסדר דברים זה. השאלה אם מסעו היה בעל אופי צבאי או למטרות שלום תלוי בשאלה אם הוא התרחש לפני או אחרי הסכם השלום שנחתם ב-1036 בין מיכאל הרביעי לבין חליף השושלת הפאטמית, מעאד' אל-מסתנצר באללה (למעשה עם אמו של החליף, במקור נסיכה ביזנטית נוצרית, מאחר שהחליף היה עדיין קטין), למרות שלא סביר שמסע זה אירע קודם לכן. היסטוריונים מודרניים מעריכים שהאראלד היה עשוי להיות בכוח שנשלח ללוות את עולי הרגל לירושלים (ככל הנראה גם חברי המשפחה הקיסרית) בעקבות הסכם השלום, שכן הוסכם גם שהביזנטים יורשו לשקם את כנסיית הקבר. יותר מכך, מצב זה הציב בפני האראלד את ההזדמנות להילחם כנגד השודדים שהתנכלו לעולי הרגל הנוצרים.
ב-1038 הצטרף האראלד לביזנטים במסעם לסיציליה, במסגרת ניסיונו של גאורגיוס מניאקיס לכבוש את האי מידי הסרצנים, שהקימו את עליו את אמירות סיציליה. במהלך המסע לחם האראלד לצדם של שכירי חרב נורמנים כמו ויליאם "זרוע הברזל". לפי סנורי סטורלוסון כבש האראלד ארבע ערים בסיציליה. ב-1041, כאשר תמה משימתו של חיל המשלוח הביזנטי בסיציליה, פרץ מרד לומברדי-נורמני בדרום איטליה והאראלד הוביל את המשמר הורנגי במספר קרבות. האראלד לחם יחד עם מושל איטליה הביזנטי, מיכאל דוקיאנוס, כשבתחילה צלחה דרכם, אך הנורמנים, בהנהגתו של בעל בריתם לשעבר, ויליאם "זרוע הברזל", הביסו את הביזנטים בקרב אוליבנטו שהתחולל במרץ ובקרב מונטה-מג'ורה שהתחולל במאי. לאחר התבוסה נקראו האראלד והמשמר הורנגי לשוב לקונסטנטינופול, בעקבות מאסרו של מניאקיס על ידי הקיסר ועקב סיבות נוספות. לאחר מכן נשלחו האראלד והמשמר הורנגי לבולגריה, לשם הם הגיעו בסוף שנת 1041. בבולגריה לחם האראלד במסגרת צבאו של מיכאל הרביעי ועסק בדיכוי המרד הבולגרי בהנהגת פטר דליאן, אירוע שמאוחר יותר ניתן בזכותו להאראלד הכינוי "מבעיר בולגריה" (Bolgara brennir) על ידי משורר החצר שלו.
לעימות בין מיכאל הרביעי לבין מניאקיס לא הייתה השפעה על האראלד והוא קיבל את הכבוד וההוקרה עם שובו לקונסטנטינופול. בספר יווני, שנכתב בשנות השבעים של המאה ה-11, "האסטרטגיה של קקאומנוס" (Στρατηγικὸν τοῦ Κεκαυμένου), נאמר ש"ארלטס" (האראלד) מצא חן בעיני הקיסר. הספר מציין שהקיסר העניק להאראלד קודם כל דרגת πρωτοσπαθάριος במשמר הקיסרי לאחר המערכה בסיציליה. לאחר המערכה נגד הבולגרים, שבה שירת האראלד בהצטיינות, הוא הועלה לדרגת σπαθαροκανδιδᾶτος, השלישית בסולם הדרגות הביזנטי שהייתה מוענקת בדרך כלל לבעלי ברית זרים של הקיסר. ה"אסטרטגיה של קקאומנוס" מציין שהדרגה שהוענקה להאראלד הייתה נמוכה יחסית. על פי דברי משורר החצר של האראלד, תיודולף ארנורסון, הוא השתתף ב-18 קרבות גדולים במהלך שירותו אצל הביזנטים. עד מהרה, לאחר מותו של מיכאל הרביעי בדצמבר 1041, סר חנו של האראלד בחצר הקיסרית, ולאחר מכן החלו העימותים בין הקיסר החדש, מיכאל החמישי קלפאטס לבין הקיסרית רבת העוצמה, זואי.
במהומה שנוצרה, נעצר האראלד והושלך לכלא, אך מידע זה שנוי במחלוקת. הסאגות מציינות שהאראלד נעצר בעוון מעשי הונאה נגד הקיסר וכן בשל רצונו להינשא לאחייניתה או נכדתה של הקיסרית שנקראה מריה (בקשתו נדחתה ככל הנראה על ידי הקיסרית, שכן היא רצתה לשאת את האראלד בעצמה). ויליאם ממלמסברי מציין שהאראלד נעצר על חילול כבודה של אשת אצולה, בעוד שעל פי סקסו גרמטיקוס ההאשמה שהועלתה נגדו הייתה רצח. דה-וירס מעלה סברה שככל הנראה הקיסר החדש חשש מפניו האראלד בשל נאמנותו לקיסר הקודם. המקורות גם חלוקים בדעתם על האופן שבו נחלץ האראלד ממאסרו, אך ככל הנראה הוא קיבל סיוע מבחוץ כדי להימלט בעיצומו של מרד שפרץ נגד הקיסר החדש. בעוד שחלק מהוורנגים נותרו לשמש כשומרי ראשו של הקיסר, היה האראלד מנהיגם של הוורנגים שתמכו במרד. בסופו של דבר נגרר הקיסר מחוץ לארמונו, עיניו נעקרו והוא הוגלה למנזר. על פי הסאגות היה האראלד זה שעיוור את הקיסר מיכאל החמישי (או לכל הפחות טען שהוא עשה זאת).