След поражението в битката при Stiklestad, Харалд успява да избяга с помощта на Rögnvald Brusason (по-късно граф на Оркни) в отдалечена ферма в Източна Норвегия.Той остана там известно време, за да излекува раните си, и след това (вероятно до месец по-късно) отпътува на север през планините към Швеция.Една година след битката при Стиклестад, Харалд пристига в
Киевска Рус (посочена в сагите като Garðaríki или Svíþjóð hin mikla).Вероятно е прекарал поне част от времето си в град Старая Ладога (Aldeigjuborg), като пристига там през първата половина на 1031 г. Харалд и хората му са посрещнати от великия княз Ярослав Мъдри, чиято съпруга Ингегерд е далечна роднина на Харалд .Силно нуждаещ се от военни лидери, Ярослав признава военен потенциал в Харалд и го прави капитан на своите сили.Братът на Харалд Олаф Харалдсон преди това е бил в изгнание при Ярослав след бунта през 1028 г. и Моркинска казва, че Ярослав е прегърнал Харалд преди всичко, защото той е брат на Олаф.Харалд участва в кампанията на Ярослав срещу поляците през 1031 г. и вероятно също се бие срещу други киевски врагове и съперници от 1030 г. като чудите в Естония,
византийците , както и печенегите и други степни номадски хора.