După înfrângerea din bătălia de la Stiklestad, Harald a reușit să evadeze cu ajutorul lui Rögnvald Brusason (mai târziu conte de Orkney) la o fermă îndepărtată din estul Norvegiei.A rămas acolo ceva timp pentru a-și vindeca rănile, iar după aceea (posibil până la o lună mai târziu) a călătorit spre nord, peste munți, până în Suedia.La un an după bătălia de la Stiklestad, Harald a ajuns în
Rusia Kievană (denumită în saga Garðaríki sau Svíþjóð hin mikla).Probabil că și-a petrecut cel puțin o parte din timp în orașul Staraya Ladoga (Aldeigjuborg), ajungând acolo în prima jumătate a anului 1031. Harald și oamenii săi au fost primiți de Marele Prinț Yaroslav cel Înțelept, a cărui soție Ingegerd era o rudă îndepărtată a lui Harald. .Având mare nevoie de lideri militari, Yaroslav a recunoscut un potențial militar în Harald și l-a făcut căpitan al forțelor sale.Fratele lui Harald, Olaf Haraldsson, fusese anterior în exil în Yaroslav în urma revoltei din 1028, iar Morkinskinna spune că Yaroslav l-a îmbrățișat pe Harald în primul rând pentru că era fratele lui Olaf.Harald a luat parte la campania lui Yaroslav împotriva polonezilor în 1031 și, probabil, a luptat și împotriva altor inamici și rivali din Kiev din anii 1030, cum ar fi Chudes din Estonia,
bizantinii , precum și pecenegii și alți oameni nomazi de stepă.