Пасля паразы ў бітве пры Стыклестадзе Харальду ўдалося збегчы з дапамогай Рогнвальда Брусасана (пазней графа Аркнейскага) на аддаленую ферму ва Усходняй Нарвегіі.Ён прабыў там некаторы час, каб залячыць раны, а пасля (магчыма, праз месяц) адправіўся на поўнач праз горы ў Швецыю.Праз год пасля бітвы пры Стыклестадзе Харальд прыбыў у
Кіеўскую Русь (у сагах яе называюць Garðaríki або Svíþjóð hin mikla).Верагодна, ён правёў прынамсі частку свайго часу ў горадзе Старая Ладага (Альдэйг'юборг), прыбыўшы туды ў першай палове 1031 г. Харальда і яго людзей вітаў вялікі князь Яраслаў Мудры, жонка якога Інгегерда была далёкай сваячкай Харальда .Яраслаў, які вельмі меў патрэбу ў военачальніках, прызнаў у Харальдзе ваенны патэнцыял і зрабіў яго капітанам сваіх сіл.Брат Харальда Олаф Харальдсан раней быў у выгнанні да Яраслава пасля паўстання ў 1028 годзе, і Маркінскіна кажа, што Яраслаў абняў Харальда перш за ўсё таму, што ён быў братам Олафа.Харальд удзельнічаў у паходзе Яраслава супраць палякаў у 1031 годзе і, магчыма, таксама ваяваў супраць іншых кіеўскіх ворагаў і супернікаў 1030-х гадоў, такіх як худа ў Эстоніі,
візантыйцы , а таксама печанегі і іншыя стэпавыя качэўнікі.