Sagaerne udtrykkeligen, „at da havde Olaf christnet alle de store Hereder i Landet“[1]. Endnu kunde vel nogle afsidesliggende, lidet tilgjængelige Fjelddale og Skovbygder hist og her være tilbage, hvorhen Christendommen ei havde formaaet at fremtrænge; men ogsaa paa dem havde Olaf sin Opmærksomhed fæstet, og hvor han ei selv personligen kunde komme at forkynde Troen, der maa man antage, at han har sendt Christenlærere i sit Sted. Inden Olafs Styrelse endte, var efter Sagaernes Vidnesbyrd hele Norge fuldkommen christnet: “der var ikke den Dal – heder det – hvori jo Indbyggerne vare christne“[2], og „ikke gaves den Afdal eller Udø i hans Rige, hvor hedensk Mand monde findes“[3].
Ligesom Olaf Tryggvessøn, saaledes udstrakte ogsaa Olaf Haraldssøn sin Omsorg for Christendommen til alle de Lande, der vare blevne befolkede af Nordmænd[4]; og som oftest gik hans Bestræbelser for Christendommen her Haand i Haand med hans Bestræbelser for at gjenvinde, eller fra ny begrunde den norske Konges Overhøihed over disse samme Lande.
Hvad Orknøerne angaar, saa bragte han ved kloge Underhandlinger Jarlerne der i det gamle Lydighedsforhold til Norge. Foranstaltninger af ham til Christendommens Befæstelse paa disse Øer omtales ikke særligen; maaskee har han fundet saadanne ufornødne paa Grund af den faste Stilling Christendommen der allerede havde indtaget, eller han har overladt det til de christne Jarler selv at bestemme det Fornødne til Kirkens Ordning.
Færøerne bragte han ogsaa til at erkjende sit Herredømme og til at betale sig Skat; og med Hensyn til dem heder det udtrykkelig, at Høvdingerne, med hvilke han underhandlede, svore ham „at holde den Lov og Landsret, som han gav“[5], derunder naturligviis indbefattet Christenretten, som altid indtog den fornemste Plads i Olafs Lovgivningsvirksomhed.
Med Island havde Olaf ligefra sin første Styrelsestid sat sig i Forbindelse ved anseede Islændinger, som efter gammel Skik jævnligen besøgte Norge og traadte i den norske Konges Tjeneste. Han havde.ved at udspørge dem, erfaret de vigtigste Brøst ved den der paa Øen gjældende Christendom, og det var naturligt, at de Indrømmelser, som ved Christendommens Lovtagning paa Althinget, vare gjorte Hedningerne, nemlig Børns Udsættelse, Æden af Hestekjød og lønligt Blot, maatte i høi Grad støde hans christelige Følelse[6]. Allerede i 1016 sendte han med Islandsfarere Bud og Jærtegn til
