Nach der Niederlage in der Schlacht von Stiklestad gelang Harald mit Hilfe von Rögnvald Brusason (später Earl of Orkney) die Flucht auf eine abgelegene Farm in Ostnorwegen.Er blieb einige Zeit dort, um seine Wunden zu heilen, und reiste danach (möglicherweise bis zu einem Monat später) über die Berge nach Norden nach Schweden.Ein Jahr nach der Schlacht von Stiklestad kam Harald in
der Kiewer Rus an (in den Sagen als Garðaríki oder Svíþjóð hin mikla bezeichnet).Wahrscheinlich verbrachte er zumindest einen Teil seiner Zeit in der Stadt Staraya Ladoga (Aldeigjuborg) und kam dort in der ersten Hälfte des Jahres 1031 an. Harald und seine Männer wurden von Großfürst Jaroslaw dem Weisen begrüßt, dessen Frau Ingegerd eine entfernte Verwandte von Harald war .Da Jaroslaw dringend militärische Führer brauchte, erkannte er das militärische Potenzial in Harald und machte ihn zum Hauptmann seiner Streitkräfte.Haralds Bruder Olaf Haraldsson war zuvor nach dem Aufstand im Jahr 1028 nach Jaroslaw verbannt worden, und Morkinskinna sagt, dass Jaroslaw Harald in erster Linie umarmte, weil er der Bruder von Olaf war.Harald nahm 1031 an Jaroslaws Feldzug gegen die Polen teil und kämpfte möglicherweise auch gegen andere Kiewer Feinde und Rivalen der 1030er Jahre, wie die Chuden in Estland, die
Byzantiner sowie die Petschenegen und andere Steppennomaden.