Происхождение большинства из этих удивительных преданий следует искать, вероятно, все в том же непонимании природы и в желании найти объяснение всему, что представлялось необычным; отсюда такое множество поверий о сверхъестественных существах. То, что язычество приписывало богам Вальхаллы и могучему Тору, искусные проповедники католицизма несомненно перенесли на могущественного гонителя веры в асов, чей топор заменил собой Мьелльнир Тора, а прославленный в преданиях скакун — упряжку козлов бога грома. Собственная слава Олава, рассказы благочестивых пилигримов и монашеские легенды постепенно превратили святого Олава в героя, которого невежественное и суеверное население считало способным на самые невероятные деяния.
В Норрланде рассказывают следующее предание о возведении первой в Норвегии церкви.
Однажды святой Олав бродил по лесам и горам в глубоком раздумье, гадая, как, не возлагая тяжелого бремени на народ, возвести замысленную церковь невиданного величия. Ему повстречался человек великанского роста, который спросил, о чем он задумался. «Как мне не задумываться, — ответил конунг, — если я дал обет построить церковь, больше и прекраснее которой нет в целом мире». Тогда тролль — а это был тролль — взялся к определенному сроку построить такое здание, с условием, что, если работа будет закончена к сроку, святой Олав отдаст ему солнце и луну и себя самого в придачу. Конунг согласился на это условие, решив про себя измыслить столь огромное здание, чтобы тролль никак не успел выстроить его к назначенному сроку. Церковь была так просторна, что семеро священнослужителей могли проповедовать в ней, не слыша и не мешая друг другу. Колонны и украшения, как внутри, так и снаружи, должны быть из самого твердого кремня; и еще множество не менее трудных условий были включены в договор. Однако гораздо скорее, чем требовалось по договору, церковь, как увидел святой Олав, была готова, и осталось только установить шпиль. Увидев это, конунг снова удалился в леса и горы в глубокой тревоге, думая о несчастливом уговоре. Вдруг он услышал из горы плач ребенка и голос великанши, успокаивавшей его такой песней:
Тут конунг безмерно обрадовался, потому что тролли, как известно, всегда теряют силу, стоит христианину назвать их по имени. Вернувшись, он увидел великана, стоящего на вершине башни и устанавливающего шпиль, и крикнул ему;
Тут же тролль со страшным криком рухнул с высоты и разбился вдребезги. Осталась от него только куча кремневых осколков. По другой версии тролля звали Слэтт, и Олав крикнул:
Еще в одной версии этой легенды тролля звали Бластер, и Олав крикнул:
То же предание распространено и в других областях Норвегии. Тролля называют Скалле, а возводит он величественный собор Нидароса (Дронтхейма). Схожее поверье, касающееся имени демонов, известно и в Германии.
Разъезжая по стране и утверждая христианскую веру, святой Олав посетил селение на восточном берегу Гломмена, которое, вместе с церковью и приходом, следующим образом получило свое название Валер.