Ikke før hadde Olav satt sin fot på norsk jord, før han fikk høre at Erik jarls sønn, den unge Håkon, var på reise med bare ett skip. Ved en krigslist fikk Olav veltet båten hans og tatt jarlesønnen til fange. Han ga ham grid på den betingelse at han forlot landet og drog til sin far, Erik jarl i England. Så seilte Olav sør- og østover langs kysten til Viken. Derfra til fots til hjemlige trakter på Opplandene hvor han kunne vente mest støtte. Den hjemvendte sjøkongen ble staselig mottatt av moren Åsta og stefaren Sigurd Syr. Begge lovet å støtte ham som best de kunne. Så la Olav sin sak frem for storbønder og småkonger på Opplandene. Det ble talt meget om dette høvdingene seg imellom. Det endte med at de tok ham til overkonge. Noen nasjonal begeistring lå nok ikke bak denne avgjørelsen. Det har vel heller demret for dem at rikskongedømmet i lengden ikke var til å unngå. Så de fikk bare håpe på at den nye overkongen ikke blandet seg for mye opp i deres lokale forhold. De var alle hedninger. Kristningsverket lot Olav foreløpig bero. Olav fikk seg skip og mannskap og la kursen vestover langs kysten. Ved Nesjar i Langesundsfjorden vant han et stort sjøslag mot Svein jarl, som etter nederlaget dro til Sverige og døde kort tid etter. Etter slaget ble han tatt til konge over hele Viken og Agder. Han seilte så rakt til Trøndelag. Denne landsdelen var nå høvdingløs etter at jarlene hadde forlatt landet. Han ble hyldet på Øreting og slo seg ned på Nidarnesset. Her reiste han hus og bygget Klemenskirken. Snart etter ble han tatt til konge også i Inntrøndelag. Så seilte han sørover igjen. På ting etter ting ble han tatt til konge. På Sola levde den siste stormann som ennå ikke hadde gitt seg inn under ham. Det var den mektige "rygekongen" Erling Skjalgsson. Han var en av de stormenn som hadde kjempet mot han ved Nesjar. Det ble inngått forlik mellom Erling og Olav på Kvitsøy i Ryfylkeleia. Men kong Olav gikk ikke med på de krav Erling stilte for seg og ætten sin. Så noe virkelig vennskap ble det nok aldri mellom de to.Etter å ha blitt tatt til konge over hele Midt- og Sør-Norge, ordnet han sitt forhold til Sverige. Sveakongen hadde lite til overs for Olav, men etter lange forhandlinger og mye kjefting endte det med at Olav fikk tilbake Ranriket (Båhuslen). Forliket skulle besegles med et giftemål. Olav skulle få sveakongens datter, Ragnhild. Men da bryllupet skulle stå på norsk side av svenskegrensen, kom det ingen brud. Faren hadde giftet henne bort til fyrst Jaroslav, som var overherre i Novgorod. Olav tok dette tungt. Skal vi tro sagaen, var det oppstått en avstandsforelskelse mellom kongsdatteren og den hjemvendte sjøkongen. Det ble gjort bot på sveakongens svik ved at hans andre datter med en trellkvinne - Astrid het hun - rømte hjemmefra og bød seg frem for kong Olav som erstatning for søsteren. Olav tok imot tilbudet og giftet seg med henne.
Da kongen hadde ordnet så noenlunde etter eget ønske sørpå, la han veien nordover til Hålogaland hvor han ble tatt til konge på de lokale tingene også over denne landsdelen. Nå var han - ihvertfall i navnet - konge over hele Norge.