Когда Олаф достиг зрелости, на корабле он отплыл в Балтику, чтобы приобрести опыт набегов; сперва он направился на остров Борнхольм и получил много добычи. Он женился на принцессе вендов и какое-то время правил землями к югу от Балтийского моря, но, когда его жена умерла, он вновь вернулся к жизни викинга, стал разбойничать в Нидерландах и на саксонском берегу и кормить воронов мясом фризов. Затем его взгляд пал на острова к западу, и рассказывают, что он совершил долгое путешествие по охотничьим угодьям викингов от Шотландии до острова Мэн, под конец совершив набеги на Ирландию, Уэльс и острова Силли. Вероятно, Олаф был предводителем флота викингов, который сражался в бою при Мэлдоне, и получил от англичан огромную сумму в качестве данегельда (налога, собиравшегося в Англии для уплаты выкупа викингам). После неудачного нападения на Лондон Олаф согласился принять солидную дань, пообещав больше не вторгаться в английские земли; одно из условий этого соглашения требовало, чтобы он принял христианство, а король Этельред был его крестным отцом, хотя некоторые источники и говорят, что к тому времени викинга уже обратил в новую веру некий подвижник на островах Силли. Так или иначе, Олаф стал теперь заметным богачом и христианином, по крайней мере номинально, женился на принцессе королевства дублинских викингов (если верить Снорри) и с верным псом по кличке Виги, который мог различать овец и коров по их клеймам, отправился в Ирландию. Что более важно, легенда об Олафе росла, и теперь он приобрел репутацию, которая собирала вокруг него наемников. Этому профессиональному викингу пришло время вернуться на родину и попытаться занять трон.
В те времена Норвегией из своих родовых владений на западе страны правил могущественный ярл Хакон. Он был ревностным поклонником скандинавских богов и прослеживал родословную своей династии до Одина, потому без энтузиазма согласился принять крещение, навязанное ему после неудачного похода на юг датским королем. Хорошо было известно, что ярл Хакон высадил миссионеров с судна, как только его флот был готов к отплытию, и провел масштабное жертвоприношение Одину на острове у побережья Швеции, на которое бог в знак своей признательности направил двух воронов, огласивших окрестности криком. Этого человека поэты называли «Тюром чаши для жертвенной крови» и «Ньёрдом бегущих врагов»: говорят, что он отправил восседать с Одином в Вальхалле девять человек королевской крови, а его победы, как считалось, обеспечивались родством с богами. Но хотя ярл-язычник Хакон и был по нраву Одину и своим языческим подданным на западе, он повздорил со старыми трондхеймскими семействами; и Олаф Трюггвассон, прибыв с флотом из Ирландии, быстро заручился поддержкой влиятельных людей. Как передает Снорри, ярл Хакон – этот верный приверженец старых богов – был убит своим рабом, скрываясь в свинарнике, и Олаф стал королем страны, из которой он был изгнан много лет назад.
Сообщают, что Олаф распространил свою власть на всю Норвегию и насаждал христианство среди не интересующегося пока этой верой населения с той же решимостью, что позволила ему стать вожаком шайки викингов и подчинила своенравных вождей его воле. Нам рассказывают, что он поверг истуканов в храме Трондхейма, публично бросив вызов скандинавским богам: он ударил Тора своим оружием и повалил его на пол. Тех, кто отказывался обратиться в христианство, он казнил так, чтобы подавить волю к сопротивлению у других. Одному влиятельному земледельцу через горло внутрь запустили змею, чтобы она прогрызла себе путь наружу; тех, кто практиковал магию, известную как сейд, он сжигал заживо на пирах в своем дворце. Говорят даже, что однажды одноглазый путник добился личной аудиенции у короля и проговорил с ним до поздней ночи, рассказывая правителю истории о его предках; этим странником был Один, пытавшийся изменить курс Олафа и отвратить его от хождения в храм, на мессы. На следующий день найти его не смогли, и Олаф поклялся прогнать его, если он явится еще раз. Возможно, именно непреклонность Олафа в насаждении избранной им веры стала причиной его гибели: помолвка со шведской принцессой была расторгнута, когда она отказалась оставить прежних богов, и он приобрел могущественного врага, назвав ее языческой собакой и ударив своей перчаткой. А стремление забрать себе вендские земли, полагавшиеся ему по первому браку, вынудило его пойти в поход в Южную Прибалтику, что дало его противникам долгожданный шанс: когда великий викинг отплывал из дома всего на одиннадцати кораблях, на него напали из засады.