Matapos ang pagkatalo sa Labanan ng Stiklestad, nagtagumpay si Harald na makatakas sa tulong ni Rögnvald Brusason (mamaya Earl ng Orkney) sa isang malayong bukid sa Eastern Norway.Nanatili siya roon nang ilang oras upang pagalingin ang kanyang mga sugat, at pagkatapos noon (marahil hanggang isang buwan mamaya) ay naglakbay pahilaga sa ibabaw ng mga bundok patungo sa Sweden.Isang taon pagkatapos ng Labanan sa Stiklestad, dumating si Harald sa
Kievan Rus ' (tinukoy sa mga alamat bilang Garðaríki o Svíþjóð hin mikla).Malamang na ginugol niya ang hindi bababa sa bahagi ng kanyang oras sa bayan ng Staraya Ladoga (Aldeigjuborg), pagdating doon noong unang kalahati ng 1031. Si Harald at ang kanyang mga tauhan ay tinanggap ni Grand Prince Yaroslav the Wise, na ang asawang si Ingegerd ay isang malayong kamag-anak ni Harald .Malubhang nangangailangan ng mga pinuno ng militar, nakilala ni Yaroslav ang potensyal ng militar sa Harald at ginawa siyang kapitan ng kanyang mga pwersa.Ang kapatid ni Harald na si Olaf Haraldsson ay dati nang naka-exile sa Yaroslav kasunod ng pag-aalsa noong 1028, at sinabi ni Morkinskinna na niyakap ni Yaroslav si Harald una at higit sa lahat dahil siya ay kapatid ni Olaf.Nakibahagi si Harald sa kampanya ni Yaroslav laban sa mga Poles noong 1031, at posibleng nakipaglaban din sa iba pang mga kaaway at karibal ng Kievan noong 1030s gaya ng Chudes sa Estonia,
Byzantines , pati na rin ang mga Pechenegs at iba pang mga steppe nomad na tao.