Наш древний паломник, игумен Даниил, свидетельствует о пребывании Олега на острове Родосе в продолжение двух лет.
Наконец, он успел спастись из Греции, вернулся в Тмуторакань, переходившую, между тем, из рук в руки у праздношатавшихся княжичей, овладел ею и перебил хозаров, участвовавших в убийстве брата и его заточении.
Десять лет княжил Олег на этом отдаленном острове, и о нем ничего не было слышно; наконец, он дождался своего часа: Всеволод умер, половцы рассыпались по Русской земле и разбили соединенных князей.
Олег увидел, что может воспользоваться поражением и бессилием своих врагов и возвратить себе отеческое наследие, ими захваченное. Он призвал половцев, своих старых приятелей, с которыми уже два раза приходил воевать Русь и, оставя Тмуторакань, появился под Черниговом.
Владимир, княживший там спокойно пятнадцать лет, не смог ему противостоять: он затворился было в городе и бился восемь дней. Половцы, между тем, грабили везде, жгли и палили села, монастыри. Добрый князь сжалился о бедствии христиан, заключил с Олегом мир. «Дружина моя билась с ними, говорил сам Мономах, о малую греблю; восемь дней мы не впускали их в острог, но, сожалея о христианских душах, о селах и монастырях горящих, я сказал, чтобы не хвалились поганые, и отдал брату отца его место, а сам пошел в Переяславль на отца своего место. Мы выступили из Чернигова на день святого Бориса и ехали сквозь полки половецкие, не восте дружины, с женами и детьми. Половцы облизывались на нас, как волки, от перевоза и с горы, но Бог и святой Борис не дали им меня в корысть; дошли невреженые до Переяславля».
Половцы пустились воевать по окрестностям, с согласия самого Олега, чем и приобрел он себе дурную славу, которая перешла ко всему его потомству.
Набеги половецкие продолжались. Владимир Мономах с братом, великим князем Святополком, не могли оставить половцев без отмщения и наказания. Послы их, пришедшие с миром, были предательски убиты в Переяславле. Святополк и Владимир пошли войной и звали с собой Олега. Тому, разумеется, нельзя было подняться на своих союзников и благодетелей. Он обещал, но не пошел.
Князья опустошили половецкие земли и, возвратившись, «начаста гнев имети на Олега, яко не шедшу ему с нима на поганые, иже погубили суть землю Русскую».
Они требовали у Олега, чтобы он выдал им Итларевича или убил его, «то есть ворог Рустей земле». Олег не согласился.
В 1096 году Святополк и Владимир потребовали к себе Олега на совет. «Не пристало судить меня ни епископам, ни игуменам, ни смердам», отвечал гордый князь, питавший ненависть к братьям, а может быть, и опасаясь их измены, — и те решили усмирить его.
Он бежал из Чернигова в Стародуб, 3 мая, в субботу, и заперся там. Осада продолжалась 33 дня. Олег, в крайности, вышел, наконец, просить прощения у братьев и обещал придти в Киев на их зов вместе с братом, Давыдом смоленским, но не подумал исполнить своего обещания; напротив, непреклонный, он кинулся в другую сторону.
Взяв у брата в Смоленске дружину, он появился в Рязани и оттуда стал требовать Мурома, принадлежавшего к отчине Святославова рода, у сына Мономаха, Изяслава, его крестника, который, придя из Курска, захватил город, пользуясь смутами. «Ступай, сказал он, в волость отца своего, в Ростов, я хочу сам сесть в Муроме и положить отсюда мир с отцом твоим. Он выгнал меня из моего отцовского города, ты ли не хочешь отдать мне здесь моего хлеба?» Изяслав не послушался, надеясь на множество воинов, собранных из Суздаля, Ростова, Белоозера, и встал перед городом. Олег надеялся на свою правду, — «он был прав», говорит летописец, — и пошел на него полком. Они сошлись, — брань была лютая, — Изяслав был убит; воины его побежали, одни через лес, другие в город. Олег вошел в Муром, и граждане приняли его.
Он пленил там вдову Изяслава, захватил ростовцев, суздальцев, белозерцев, и велел сковать их. Тогда вздумал он воспользоваться благоприятными обстоятельствами и пошел на Суздаль. Суздальцы приняли его. Олег пошел дальше на Ростов и также занял город. Таким образом, он подчинил себе под власть всю землю Суздальскую и Ростовскую, посажал посадников по городам и начал брать дань.
Брат убитого, другой сын Владимира, крестник Олега, Мстислав новгородский, прислал к нему посла сказать: «Иди из Суздаля в свой Муром и в чужой волости не сиди, а я пошлю молиться к отцу и помирю тебя с ним, хоть ты и убил моего брата. Делать нечего: в ратях погибают мужи и цари».
Мстислав в самом деле послал посла к отцу просить его о мире с Олегом, и тот написал письмо к своему строптивому двоюродному брату и куму.
Олег не послушался ни Мономаха, ни Мстислава. Предприимчивый, он замышлял захватить и Новгород и послал вперед в сторожах младшего брата Ярослава, который остановился на Медведице.