Po kilkuletniej służbie u Jarosława, już jako znany powszechnie wojownik, Harald na czele swoich ludzi udał się do Konstantynopola, gdzie wstąpił do gwardii wareskiej – istniejącej od X wieku straży przybocznej cesarza wschodniego cesarstwa rzymskiego. Wysoki, potężnie zbudowany i wojowniczy Norweg szybko zaskarbił sobie uznanie gwardzistów, stając się w krótkim czasie ich dowódcą. Harald brał udział w walkach w wielu zakątkach imperium. Szlak bojowy zaprowadził go na Morze Śródziemne, gdzie walczył przeciwko arabskim piratom, a także do Anatolii, Mezopotamii i północnej Afryki, gdzie według skalda Þjóðólfra Arnórssona miał zdobyć ponad osiemdziesiąt twierdz. Służba w gwardii zaprowadziła przyszłego króla Norwegii nawet do Jerozolimy. Charakter jego wizyty pozostaje niepewny, ale najprawdopodobniej miała ona miejsce po podpisaniu traktatu pokojowego między cesarzem Michałem IV Paflagończykiem a kalifem z dynastii Fatymidów al-Mustansirem Billahem w 1036 roku. Zadaniem Haralda było wówczas eskortowanie do miasta pielgrzymów, wśród których byli również członkowie rodziny cesarskiej.
Seria zwycięskich kampanii z udziałem Haralda dobiegła końca w 1038 roku wraz wyprawą przeciwko emiratowi Sycylii. Wówczas dowódca gwardii wareskiej walczył wspólnie z najemnikami Wilhelma Żelaznorękiego, twórcy potęgi rodu de Hauteville i pierwszego normańskiego hrabiego Apulii. Po kampanii sycylijskiej normańscy najemnicy i Lombardczycy wzniecili w 1041 roku bunt przeciwko bizantyjskiemu panowaniu w południowych Włoszech. Cesarskie wojska, w tym gwardia wareska Haralda, zostały pokonane 17 marca w bitwie pod Olivento i 4 maja pod Montemaggiore. Po tych klęskach gwardia została odesłana do stolicy, a następnie do Bułgarii, gdzie walczyła u boku cesarza przeciwko rebeliantom.