Гибель Изяслава и вторичное вокняжение Всеволода в Киеве привели к новому перераспределению волостей. По свидетельству летописи, «Всеволод сел в Киеве, на столе отца своего и брата своего, приняв власть над всей Русской землей» и «посадил сына своего Владимира в Чернигове, а Ярополка во Владимире, придав ему еще и Туров». При таком раскладе сил он оказался естественным лидером княжеского рода в качестве единственного «старшего» князя на Руси, но сам княжеский род продолжал оставаться раздробленным, так как Всеволод удовлетворил наследственные права только Изяславичей, оставив под их управлением те волости, которые подчинялись Изяславу. Святославичи были по-прежнему исключены из этой политической конфигурации, и этот факт подготавливал почву для дальнейших столкновений.

Первое место в новой политической системе принадлежало Владимиру Мономаху, который в 25 лет стал князем второго по значению города «Русской земли». Вероятно, это случилось после того, как восставшие черниговцы, потеряв всякую надежду из-за бегства Олега с поля сражения, прекратили оказывать сопротивление Всеволоду Ярославичу. Впрочем, из «Поучения» Мономаха следует, что после битвы на Нежатиной Ниве он отправился не в Чернигов, а в Переяславль и «встал в Оброве», видимо, для того, чтобы организовать сопротивление половцам. Затем Мономаху — уже в качестве князя Черниговского — пришлось отправляться к месту своего прежнего княжения — в Смоленск, который в этой кризисной ситуации, по-видимому, остался без надлежащего присмотра, чем не замедлил воспользоваться Всеслав Полоцкий, устроивший пожар в городе. В «Поучении» Мономах пишет: «…Всеслав Смоленск пожег, и я с черниговцами, вскочив на коней, и с запасными конями помчался и не застал… в Смоленске. В том же походе против Всеслава я пожег землю и, повоевав ее до Лукомля и Логожьска, пошел войною на Друцк, а потом — к Чернигову».

По всей видимости, эта экспедиция была предпринята Мономахом поздней осенью 1078 г. Однако это была не последняя его кампания в этом году, так как далее читаем: «А в ту зиму повоевали половцы Стародуб весь, и я пошел с черниговцами и с половцами, и на Десне захватил в плен князей Асадука и Саука и дружину их перебил. А на утро за Новым Городом (Новгородом-Северским. — Д.Б.) разбили сильное войско Белкатгина, а семечей и всех пленников отняли». В этом фрагменте следует обратить внимание на то, что в борьбе с одними половецкими ордами Владимир Мономах, по-видимому, делал ставку на другие.

Факты, приведенные в «Поучении», позволяют предполагать, что отношение князя к кочевникам на протяжении его политической деятельности не было неизменным: в конце 1070-х гг. он при случае использовал половцев в качестве союзников и лишь позднее стал выступать в качестве организатора сопротивления половецкой агрессии, образ которого был запечатлен на страницах «Повести временных лет». Летопись сохранила упоминание о том, что в 1080 г. по приказанию отца Владимир Мономах предпринял поход на «переяславских торков» — федератов, живших на южных рубежах «Русской земли», которые «заратились на Русь», но были побеждены.

Летом 1079 г. получила продолжение борьба за наследство Святослава Ярославича, которую на сей раз возглавил пришедший на Русь с половцами тмутороканский князь Роман, по-видимому оставивший на княжении в Тмуторокани вместо себя брата Олега. Против него выступил сам Всеволод Ярославич, ставка которого располагалась у Переяславля. В результате переговоров ему удалось заключить мир с кочевниками, которые вернулись обратно в степь, убив по дороге своего союзника Романа. Вскоре после этого его брат Олег был захвачен некими «хазарами» (вероятно, представителями хазарской общины Тмуторокани) и выслан в Константинополь, а на его место из Киева или Чернигова прислан посадник Ратибор.

Все эти действия выглядят идеально скоординированными и поразительно выгодными для киевского князя, на краткое время подчинившего своей гегемонии все русские княжества, так что именно здесь складывается впечатление о его тайной причастности к этим акциям, позволившим на короткое время подавить оппозицию «младших» князей. Из Константинополя Олег Святославич, по-видимому, был отправлен в ссылку на остров Родос, где по свидетельству русского путешественника начала XII в. игумена Даниила провел два года. Затем положение князя-изгнанника улучшилось: Олег был не только возвращен с Родоса, но и сумел войти в круги византийской аристократии, женившись на знатной гречанке Феофано Музалон.

Вероятно, с византийской помощью он в 1083 г. и вернулся в Тмуторокань, где к тому времени уже не было киевского посадника Ратибора: того в 1081 г. изгнали из города новые представители княжеской оппозиции, которые не имели своих волостей, — Давыд Игоревич и Володарь Ростиславич, внук и правнук Ярослава Мудрого. Олег Святославич арестовал своих родственников и расправился с хазарами, которые прежде советовали убить его брата (Романа) и его самого. Хотя Олег отпустил бывших правителей Тмуторокани на свободу, один из изгнанников, Давыд Игоревич, блокировал торговые пути устья Днепра (в Олешье), совершив нападение на караван византийских купцов. В ситуацию был вынужден вмешаться киевский князь, распорядившийся в 1084 г. привести племянника в Киев и дать ему Дорогобуж, который был центром Погорины, граничившей с Киевской землей.

Вопрос об изначальной принадлежности этой волости является предметом споров: большинство исследователей, вслед за С.М. Соловьёвым, считают, что прежде эта волость подчинялась волынскому князю Ярополку Изяславичу, а меньшинство поддерживают предположение В.Н. Татищева о том, что Погорина была выделена из состава Киевской земли, но на нее претендовал Ярополк Изяславич. Дальнейшее развитие событий, описанное в «Повести временных лет» под 1085–1086 гг., скорее указывает на то, что киевский князь осуществил этот акт за счет волынского князя Ярополка, что и привело к конфликту 1085–1086 гг., хотя между ними определенно существовала общность стратегических интересов, на которую указывал М.С. Грушевский, писавший, что Всеволод Ярославич и Ярополк Изяславич удерживали за собою волости, оспариваемые князьями-изгоями, так что вряд ли они стали портить отношения из-за приграничной территории — тем более учитывая тот факт, что за год перед этим волынский князь был вынужден прибегнуть к помощи киевского князя.

Согласно «Повести временных лет», недоразумения на Волыни начались еще в 1084 г., под которым в летописи записано: «Приходил Ярополк к Всеволоду на Пасху. В это же время побежали два Ростиславича от Ярополка и, придя, прогнали Ярополка, и послал Всеволод Владимира, сына своего, и выгнал Ростиславичей, и посадил Ярополка во Владимире». Далее в летописи следует упоминание о наделении мятежного Давыда Игоревича княжением в Дорогобуже, а под 1085 г. в летописи читаем, что Ярополк «хотел идти на Всеволода, послушав злых советников», однако это намерение не осталось тайной для киевского князя, который, узнав об этом, послал против него Владимира Мономаха. По-видимому, мятеж был плохо подготовлен, либо Ярополк не ожидал столь стремительной реакции из Киева, так что, оставив свою мать и дружину в Луцке, бежал в Польшу. «Когда же Владимир пришел к Луцку, сдались лучане. Владимир же посадил Давыда во Владимире на место Ярополка, а мать Ярополка, и жену его, и дружину его привел в Киев и имущество его взял». Однако, судя по всему, конфликт между ними не был глубоким, так как, вернувшись из Польши в 1086 г., Ярополк «сотворил мир с Владимиром, и пошел Владимир назад к Чернигову. Ярополк же сел во Владимире».