Μετά την ήττα στη μάχη του Stiklestad, ο Harald κατάφερε να δραπετεύσει με τη βοήθεια του Rögnvald Brusason (αργότερα κόμης του Orkney) σε ένα απομακρυσμένο αγρόκτημα στην Ανατολική Νορβηγία.Έμεινε εκεί για αρκετή ώρα για να επουλώσει τις πληγές του και στη συνέχεια (πιθανώς μέχρι και ένα μήνα αργότερα) ταξίδεψε βόρεια πάνω από τα βουνά στη Σουηδία.Ένα χρόνο μετά τη μάχη του Stiklestad, ο Harald έφτασε στη
Ρωσία του Κιέβου (αναφέρεται στα έπος ως Garðaríki ή Svíþjóð hin mikla).Πιθανότατα πέρασε τουλάχιστον ένα μέρος του χρόνου του στην πόλη Staraya Ladoga (Aldeigjuborg), φτάνοντας εκεί το πρώτο μισό του 1031. Ο Χάραλντ και οι άνδρες του υποδέχθηκαν τον Μέγα Πρίγκιπα Γιαροσλάβ ο Σοφός, του οποίου η σύζυγος Ingegerd ήταν μακρινός συγγενής του Harald .Έχοντας μεγάλη ανάγκη από στρατιωτικούς ηγέτες, ο Γιαροσλάβ αναγνώρισε ένα στρατιωτικό δυναμικό στο Χάραλντ και τον έκανε αρχηγό των δυνάμεών του.Ο αδελφός του Χάραλντ, Όλαφ Χάραλντσον, ήταν προηγουμένως εξόριστος στο Γιαροσλάβ μετά την εξέγερση του 1028, και ο Μορκινσκίννα λέει ότι ο Γιαροσλάβ αγκάλιασε τον Χάραλντ πρώτα και κύρια επειδή ήταν ο αδερφός του Όλαφ.Ο Χάραλντ συμμετείχε στην εκστρατεία του Γιαροσλάβ κατά των Πολωνών το 1031 και πιθανώς πολέμησε επίσης εναντίον άλλων εχθρών και αντιπάλων του Κιέβου του 1030, όπως οι Τσούντες στην Εσθονία, οι
Βυζαντινοί , καθώς και οι Πετσενέγκοι και άλλοι νομάδες της στέπας.