Чешский поход сблизил Владимира с его двоюродным братом. Известно, что Олег стал крестным отцом первенца Владимира Мстислава, и таким образом двух князей связали узы духовного родства, которые в то время значили не меньше, чем родство по крови. Позднее крестником Олега станет и второй сын Мономаха — Изяслав, родившийся, скорее всего, весной 1078 года. Однако впоследствии, как это порой бывает, вчерашние друзья превратятся в едва ли не смертельных врагов.
Внезапная смерть Святослава 27 декабря 1076 года от неудачной операции ("резанья желве", то есть нарыва) кардинально изменила расстановку политических сил на Руси. 1 января 1077 года отец Владимира Всеволод занял киевский престол. Сам Владимир получил в княжение Смоленск. Союз с Польшей со смертью Святослава (а возможно, и еще раньше) прекратил свое существование. Этим не преминул воспользоваться Изяслав, имевший на руках и такой сильный козырь, как послание папы Григория VII польскому князю Болеславу. Еще в 1076 году он вернулся в Польшу, а в мае 1077 года вместе с польским войском двинулся на Русь. Всеволод выступил ему навстречу к Волыни. Начались переговоры, завершившиеся заключением мира. 15 июля Изяслав по соглашению с братом занял Киев, а Всеволод получил Чернигов. Надо думать, что сговорчивости Всеволода в немалой степени способствовало то обстоятельство, что еще 4 мая Чернигов попытался захватить его племянник Борис, сын бывшего смоленского князя Вячеслава Ярославича. "И бысть княженья его 8 днии, — сообщает о Борисе летописец, — и бежа Тмутороканю…". Есть основания предполагать, что именно Владимиру пришлось изгонять из Чернигова своего двоюродного брата (прямо об этом сообщает В. Н. Татищев). Борис бежал в Тьмуторокань — русский форпост на Тамани, центр небольшого княжества, которым тогда владел сын Святослава Роман. Здесь, на отдаленной окраине Русского государства, отделенной от остальной Руси безбрежной Степью, собирались силы, в равной мере враждебные и Изяславу, и Всеволоду.
Еще до вокняжения Изяслава в Киеве, зимой 1077 года, "на весну", Владимир был послан отцом к Новгороду на помощь князю Глебу Святославичу — очевидно, для борьбы с Всеславом Полоцким. Летом, уже с отцом (надо полагать, сразу после примирения Всеволода с Изяславом), Владимир совершил поход на Полоцк, о результатах которого источники не сообщают. Скорее всего, поход оказался неудачным, и зимой 1077/78 года, уже по согласованию с киевским князем Изяславом, Владимир вновь идет к Полоцку вместе с сыном Изяслава Святополком; и "ожгоша Полтескъ", как вспоминал Мономах в своем "Поучении".
Пасху 1078 года (8 апреля) Владимир встречал у отца в Чернигове. Здесь же пребывал и выведенный из Владимира (или приглашенный Всеволодом?) Олег Святославич. Черниговская резиденция Мономаха располагалась на Красном дворе, где Владимир устроил "обед", на который пригласил и отца, и двоюродного брата. Едва ли его целью не было примирение двух близких ему людей. Владимир привез отцу 300 гривен золота — огромную по тем временам сумму, и в литературе уже давно было высказано предположение, что это мог быть залог за Олега, некое обеспечение его лояльности по отношению к Всеволоду. Но если так, то Владимир просчитался. По-видимому, именно на Красном дворе произошла ссора, имевшая роковые последствия. "Повесть временных лет" как об одном из важнейших событий года сообщает о бегстве Олега из Чернигова 10 апреля 1078 года. Олег бежал в Тьмуторокань, где уже находились его родной брат Роман и двоюродный Борис — грозная коалиция племянников правивших Русью князей Ярославичей.
Суть конфликта между Всеволодом и Олегом предельно ясна — притязания обоих князей на Чернигов. Олег стремился завладеть им как городом своего отца, тем более что Святослав, несмотря на то, что умер киевским князем, был погребен — очевидно, по собственному завещанию — в кафедральном черниговском Спасском соборе. Всеволод же, в соответствии с понятиями своего времени, считал, что Чернигов должен принадлежать ему по праву старшинства. Ибо он, добровольно уступив Киев старшему брату, занял то место, которое ранее, в период "триумвирата" Ярославичей, занимал Святослав. Таким образом, столкновение двух князей — старшего и младшего, дяди и племянника — отразило столкновение двух принципов наследования или даже, шире, двух принципов политического устройства Руси — старого, основанного на родовом владении Русью всеми князьями Рюриковичами ("родовом сюзеренитете"), и относительно нового, основанного на "отчинном" владении землями (заметим, что сам этот термин — "отчина" — появляется в источниках несколько позже).
Конфликт между двумя этими началами в политической жизни Руси с особой силой проявится позднее, уже в годы киевского княжения Всеволода Ярославича. Но именно притязания князя Олега Святославича на "отчий" Чернигов стали наиболее зримым его воплощением. И исторический парадокс — а скорее, историческая закономерность — заключается в том, что князю Владимиру Всеволодовичу Мономаху, более других отдавшему борьбе с Олегом и ставшему его главным, историческим противником, суждено было в конечном итоге проводить в жизнь и утверждать те самые принципы, которые первоначально отстаивал Олег.
Пока же Владимир возвратился в Смоленск. Но уже в конце августа 1078 года ему пришлось выступить из Смоленска во главе своей дружины и двинуться к Переяславлю на помощь отцу, который 25 августа на реке Соже (в Черниговской земле) был разбит своими племянниками Олегом и Борисом, приведшими из Тьмуторокани многочисленную половецкую рать. И здесь Олег оказался своего рода новатором, впервые в истории Руси использовав для достижения своих политических целей союзных половцев. (Практика привлечения половцев на свою службу и использования их в междоусобных войнах очень скоро станет всеобщей.)
После победы на Соже Олег и Борис заняли Чернигов, "мняще одолевше, а земле Русьскеи много зло створше", как с горечью замечает летописец. Владимир "проидох сквозе половечьскыи вои, бьяся", и в Переяславле встретился с отцом. Отсюда оба направились в Киев к Изяславу, который выразил готовность помочь брату в войне с племянниками. "Аще будеть нам причастье в Русскеи земли, то обема, — приводит его слова летописец, — аще лишена будеве, то оба". Объединенная рать четырех князей — Изяслава, его сына Ярополка, Всеволода и Владимира Мономаха — подступила к Чернигову. Несмотря на отсутствие в городе Олега и Бориса, черниговцы отказались сдать город, и начался штурм. Летопись, рассказывая об этом, особо выделяет Владимира: именно он со своей дружиной, захватил восточные ворота Чернигова; "и отвориша градъ околнии, и пожгоша". Однако развить успех князьям помешало известие о подходе Олега и Бориса. 3 октября 1078 года в битве на Нежатиной Ниве (недалеко от Чернигова) старшие князья одержали решительную победу. Правда, досталась она дорогой ценой: на поле брани пал киевский князь Изяслав Ярославич, до конца исполнивший свой братский долг. Погиб и один из зачинщиков усобицы князь Борис Вячеславич, который, если верить летописи, воинственностью превосходил даже Олега. Сам же Олег с остатками дружины бежал в Тьмуторокань.
Для Всеволода и его сына это стало победой вдвойне. Всеволод как старший в роде занял киевский престол, сохранив за собой и Чернигов, и Переяславль: "переима власть Русьскую всю", по выражению летописца. Чернигов достался Владимиру. В этом городе он будет княжить почти шестнадцать лет, до 1094 года. Сыновья Изяслава сохранили за собой часть отцовских владений — но уже в качестве дарения от Всеволода. Ярополка Всеволод посадил на княжение во Владимире-Волынском, придав ему Туров. Святополк же княжил в Новгороде до 1088 года, когда Всеволод перевел его в тот же Туров, посадив на княжение в Новгороде своего двенадцатилетнего внука Мстислава, сына Владимира Мономаха.
За Святославичами остался единственный удел: удаленная от Руси Тьмуторокань. Но и ее Всеволод — правда, ненадолго — сумел прибрать к рукам. В следующем 1079 году Роман Святославич привел на Русь половцев, но у Переяславля Всеволод заключил с ними мир, и половцы отступили. На обратном пути между ними и Романом вспыхнула ссора, в результате которой Роман был убит. Трудно удержаться от предположения, что ссора эта была инспирирована киевским князем, хотя сам Олег позднее обвинял в убийстве брата тьмутороканских хазар (остатки прежнего хазарского, скорее всего иудейского, населения Тьмуторокани). В том же году хазары захватили в плен самого Олега и отправили его в Византию. О том, что их действия были согласованы со Всеволодом, кажется, свидетельствует тот факт, что хазары не оказали никакого сопротивления присланному из Киева посаднику Ратибору.
В годы киевского княжения Всеволода Ярославича (1078—1093) Владимир становится по существу соправителем отца. Он принимает участие во всех важнейших политических акциях, осуществляет на практике политику отца, а нередко и сам решает судьбы отдельных княжеств и их правителей. По его собственным словам, за эти пятнадцать лет он до ста раз совершал стремительные переезды из Чернигова в Киев, умудряясь преодолевать 130 верст, разделявших два города, всего лишь за день. В 1080 году Владимир по поручению отца выступает против "заратившихся" переяславских торков и разбивает их. Годом раньше или, может быть, позже (точная датировка невозможна), в ответ на нападение Всеслава Полоцкого на Смоленск, он совершает очередной поход на Всеслава и опустошает его земли. Затем воюет с половцами, разорившими Стародуб, причем в его войске, наряду с черниговцами, присутствуют и союзники из тех же половцев. В течение двух зим подряд Владимир ходит войной в непокорную Вятичскую землю, а затем снова воюет с половцами и тем же Всеславом.