Efter nederlaget i slaget vid Stiklestad lyckades Harald fly med hjälp av Rögnvald Brusason (senare jarl av Orkneyöarna) till en avlägsen gård i Östnorge.Han stannade där en tid för att läka sina sår och reste därefter (möjligen upp till en månad senare) norrut över bergen till Sverige.Ett år efter slaget vid Stiklestad anlände Harald till
Kievan Rus ' (i sagorna kallad Garðaríki eller Svíþjóð hin mikla).Han tillbringade troligen åtminstone en del av sin tid i staden Staraya Ladoga (Aldeigjuborg), och anlände dit under första hälften av 1031. Harald och hans män välkomnades av storprins Jaroslav den vise, vars hustru Ingegerd var en avlägsen släkting till Harald .I stort behov av militära ledare insåg Jaroslav en militär potential hos Harald och gjorde honom till kapten för sina styrkor.Haralds bror Olaf Haraldsson hade tidigare varit i exil till Jaroslav efter upproret 1028, och Morkinskinna säger att Jaroslav omfamnade Harald först och främst för att han var bror till Olaf.Harald deltog i Jaroslavs fälttåg mot polackerna 1031, och möjligen kämpade han även mot andra 1030-tals fiender och rivaler från Kiev, såsom Chudes i Estland,
bysantinerna , såväl som pechenegerna och andra stäppnomader.