Русские летописи сообщают об Олеге как о верном соратнике и родиче князя Рюрика, первого правителя Новгородской Руси, родоначальника царской династии.
Вполне вероятно, что Олег оказался в дружине Рюрика еще в ранней молодости. Несомненно, что под главенством отважного и щедрого норманнского хёвдинга он совершил немало походов в Западную и Восточную Европу. В составе отряда Рюрика Олег пришел в земли враждовавших между собой ильменских словен и финно-угорских племен.
Призвание варягов на Русь. «Повесть временных лет» говорит, что в 859 году какие-то варяги «из заморья» брали дань со словен, чуди, мери, веси и кривичей, подчинив их своей власти. В 862 году славянские и финские аборигены тех варягов прогнали, после чего между племенами начался раздор. «…И встал род на род, и была у них усобица, и стали воевать друг с другом«, — пишет летописец. Лишившись защиты и не сумев разрешить противоречий, племенные вожди постановили пригласить к себе правителя, способного восстановить покой и справедливость, и «пошли за море к варягам».
Приход Рюрика в Ладогу. Летописец не знал, в какие края отправились посланцы северных племен. Прибыв на место, они сказали: «Земля наша велика и обильна, а наряда в ней нет. Приходите княжить и владеть нами«. На призыв откликнулся Рюрик с братьями Синеусом и Трувором. Они «со своими родами» и воинами двинулись в путь. Вскоре они появились в Ладоге, или как ее называли скандинавы в Альдейгюборге. Этот город-порт, расположенный на Балтийско-Волжском водном пути, являлся столицей словенской земли. Синеус отправился «на Белоозеро», в землю племен веси и чуди. Трувор обосновался в Изборске, в краю кривичей. Рюрик вместе с дружиной остался в Ладоге. В числе его ближайших воевод и находился Олег.
Верный соратник. В 864 году Трувор и Синеус умерли, и Рюрик «принял всю власть один». Он направил своих наместников в Полоцк, Ростов, Муром и на Белоозеро. Столицу своей державы Рюрик переместил южнее, в устье реки Волхов. Там он выстроил крепость, где разместилась княжеская резиденция. Полагают, что Рюриково городище и являлось первоначальным Новгородом — новым городом по отношению к старой Ладоге. Подвластные новгородскому правителю земли охватывали Южное Приладожье, Верхнее Поднепровье, часть Поволжья, значительные территории на северо-востоке Руси. Имя Олега не названо среди наместников Рюрика. Он оставался в числе его главных советников, постоянно сопровождая правителя в военных походах и на полюдье — ежегодном сборе дани с подвластных племен.
Нареченный отец. В 870-е годы Рюрик женился на сестре Олега — Ефанде, скрепив их воинскую дружбу еще одним звеном. Когда же у новгородского князя родился сын Игорь, Олег стал его воспитателем и нареченным отцом, приняв на себя все обязанности по формированию его характера и военному обучению. По обычаям скандинавов, передача конунгом сына на воспитание умудренному опытом воину означала высшую степень доверия к нему и признание его членом своего клана.
Продолжатель дел. В 879 году князь Рюрик умер во время тяжелого военного похода. Чувствуя приближение смерти, он поручил опеку над своим малолетним сыном Олегу. Однако это вовсе не означало, что он назначил Олега регентом при наследнике. У норманнов, в случае смерти конунга, вопрос о передаче власти решал тинг — собрание «лучших людей» и воинов. Совет избирал нового правителя из числа наиболее достойных и уважаемых представителей того же рода. Старшим «в роде» Рюрика оказался Олег, он и был объявлен князем Новгородской земли.