Stiklestadin taistelun tappion jälkeen Harald onnistui pakenemaan Rögnvald Brusasonin (myöhemmin Orkneyn jaarli) avulla syrjäiselle maatilalle Itä-Norjassa.Hän viipyi siellä jonkin aikaa parantamaan haavojaan, ja sen jälkeen (mahdollisesti jopa kuukauden kuluttua) matkusti pohjoiseen vuorten yli Ruotsiin.Vuosi Stiklestadin taistelun jälkeen Harald saapui
Kiovan Venäjälle (kutsutaan saagoissa nimellä Garðaríki tai Svíþjóð hin mikla).Hän todennäköisesti vietti ainakin osan ajastaan Staraya Laatokan kaupungissa (Aldeigjuborg) saapuessaan sinne vuoden 1031 ensimmäisellä puoliskolla. Suurprinssi Jaroslav Viisas toivotti Haraldin ja hänen miehensä tervetulleeksi, jonka vaimo Ingegerd oli Haraldin kaukainen sukulainen. .Jaroslav tarvitsi kipeästi sotilasjohtajia, ja hän tunnisti Haraldin sotilaallisen potentiaalin ja teki hänestä joukkojensa kapteenin.Haraldin veli Olaf Haraldsson oli aiemmin ollut maanpaossa Jaroslavissa vuoden 1028 kapinan jälkeen, ja Morkinskinna sanoo, että Jaroslav syleili Haraldia ennen kaikkea siksi, että hän oli Olafin veli.Harald osallistui Jaroslavin kampanjaan puolalaisia vastaan vuonna 1031 ja mahdollisesti myös muita 1030-luvun Kiovan vihollisia ja kilpailijoita, kuten Viron tšudeja,
bysanttilaisia , sekä petenegejä ja muita aropaimentolaisia vastaan.