Selepas kekalahan dalam Pertempuran Stiklestad, Harald berjaya melarikan diri dengan bantuan Rögnvald Brusason (kemudian Earl of Orkney) ke ladang terpencil di Timur Norway.Dia tinggal di sana untuk beberapa lama untuk menyembuhkan lukanya, dan selepas itu (mungkin sehingga sebulan kemudian) mengembara ke utara melintasi pergunungan ke Sweden.Setahun selepas Pertempuran Stiklestad, Harald tiba di
Kievan Rus ' (disebut dalam hikayat sebagai Garðaríki atau Svíþjóð hin mikla).Dia mungkin menghabiskan sekurang-kurangnya sebahagian daripada masanya di bandar Staraya Ladoga (Aldeigjuborg), tiba di sana pada separuh pertama tahun 1031. Harald dan anak buahnya disambut oleh Putera Besar Yaroslav the Wise, yang isterinya Ingegerd adalah saudara jauh Harald .Sangat memerlukan pemimpin tentera, Yaroslav mengiktiraf potensi ketenteraan di Harald dan menjadikannya kapten pasukannya.Saudara Harald Olaf Haraldsson sebelum ini berada dalam buangan ke Yaroslav berikutan pemberontakan pada tahun 1028, dan Morkinskinna mengatakan bahawa Yaroslav memeluk Harald pertama sekali kerana dia adalah abang kepada Olaf.Harald mengambil bahagian dalam kempen Yaroslav menentang Poland pada 1031, dan mungkin juga bertempur menentang musuh dan saingan Kievan 1030-an yang lain seperti Chudes di Estonia,
Byzantine , serta Pechenegs dan orang nomad padang rumput lain.