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