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