Aasta, hans Frændes Harald Grønskes Enke, og hos hvem dennes Søn, Olaf Haraldssøn, dengang et Barn, opfostredes. Kongens Christendomsbud fandt her en velvillig Modtagelse; Sigurd Syr med hele sit Hus og mange af sine Undersaatter lode sig døbe. Kongen selv stod Fadder til den to- eller treaarsgamle Olaf Haraldssøn, der af Forsynet var bestemt til senere at spille en saa vigtig Rolle i Norges Historie. Kongens Christendomsforkyndelse skal ved denne Leilighed ogsaa have strakt sig videre over Oplandene og her ikke have været ganske uvirksom; imidlertid var det ikke Olaf Tryggvessøn forbeholdet at styrte Hedendommen eller skaffe Christentroen noget Grundfæste i denne Landsdeel.
Medens Olaf opholdt sig i Viken om Vinteren 997–998 stræbte han her at udrydde alle Hedendommens Levninger. Især var hans Opmærksomhed henvendt paa alle dem, som øvede Trolddom, Seid og Galder. Han fik lokket en heel Flok af saadanne Troldmænd til sig, og da han ei kunde bevæge dem til at antage Christendommen, lod han dem indebrænde.
Under denne sin Virksomhed i den sydlige Deel af Norge havde Olaf ikke tabt den nordligste af Sigte. Haalogalands Omvendelse stod ham fremdeles for Øie, og han forberedte den med megen Sluhed. Han drog om Sommeren 998 igjen langs Kysten nordefter til Throndhjem. Paa denne Reise traf han af en Hendelse to anseede Brødre fra Haalogaland, som han hemmelig vandt for sin Sag. Ved deres Hjælp fik han den mægtige og kloge Haarek af Thiotta bragt fangen til Throndhjem i sin Vold, og slap ham først fri, efterat han hemmelig havde lovet Kongen sin Bistand. Haarek kom hjem, tilsyneladende fremdeles fiendsk sindet mod Olaf. Han fik rinder Paaskud af en nødvendig Raadslagning om Haalogalands Forsvar mod Kongen, lokket den anden af Haaleygernes Høvdinger, Eyvind Kinnrifa, til sig og spillede ham i Hænderne paa Kongens Mænd, der førte ham fangen til Nidaros. Olaf søgte ogsaa at vinde ham, men Eyvind var ubevægelig og maatte ende sit Liv rinder de frygteligste Pinsler.
Olaf havde naaet sit Maal, at svække Haaleygernes Modstandskraft. Da han om Sommeren 999 med en stor Flaade kom til Haalogaland, gik Haarek strax Kongen til Haande, lod sig døbe og fik til Gjengjæld store Forleninger. Uden Hinder christnedes nu den sydlige Deel af Landet. De nordlige Haaleyger lavede sig derimod til Kamp under Anførsel af sine Høvdinger, Thorer Hjort og Rand hiin Ramme. De mødte Kongen med en betydelig Stridsmagt, men bleve slagne. Thorer blev dræbt paa Flugten. Rand undkom, men faldt dog strax efter i Kongens Hænder. Da han ei vilde lade sig døbe, blev han
