В годы киевского княжения Всеволода Ярославича (1078—1093) Владимир становится по существу соправителем отца. Он принимает участие во всех его важнейших политических акциях, осуществляет на практике политику отца, а нередко и сам решает судьбы отдельных княжеств и их правителей. По его собственным словам, за эти пятнадцать лет он до ста раз совершал стремительные переезды из Чернигова в Киев, умудряясь преодолевать 130 верст, разделявших два города, всего лишь за день.
После смерти Всеволода 13 апреля 1093 года в руках Владимира оказалась реальная власть над Киевом. Однако принцип наследования отцовских владений еще далеко не утвердился в Русской земле. Права на Киев принадлежали всему Ярославову роду, ибо Киев воспринимался не столько как «отчина», сколько как «дедина» русских князей. Старшим же среди внуков Ярослава Мудрого считался двоюродный брат Владимира Мономаха князь Святополк Изяславич, княживший в то время в Турове.
Летопись так передает размышления Владимира: «Аще сяду на столе отца своего, то имам рать съ Святополком взята, яко есть стол преже от отца его был». «Размыслив», Владимир послал за Святополком в Туров, а сам ушел обратно в Чернигов. Святополк стал киевским князем.
Этот добровольный уход из Киева открыл черную полосу в жизни Владимира Мономаха — полосу жесточайших неудач, безвозвратных утрат и горьких разочарований. Но случилось так, что именно в этот тяжелейший для себя период Владимир сумел утвердить свой нравственный и политический авторитет в русском обществе, стать не просто одним из наиболее влиятельных, но, несомненно, самым влиятельным среди всех русских князей — во всяком случае, именно таким изображает его летописец.
24 апреля 1093 года Святополк вступил в Киев. А уже спустя несколько дней началась новая большая война с половцами, принесшая много несчастий и княжескому семейству, и всему населению Руси. 26 мая, в самый праздник Вознесения Господня, в битве на реке Стугне (правом притоке Днепра) у Треполя Владимир и Святополк потерпели сокрушительное поражение от половцев. Виновником случившегося киевский летописец называет князя Святополка Изяславича, который отказался прислушаться к увещеваниям Мономаха и заключить мир с половцами. Расплачиваться же за его гордыню и скупость (ибо одной из причин отказа от мира было нежелание платить половцам положенное в таких случаях вознаграждение) пришлось всей Русской земле. Владимир пережил тогда и личную драму. При отступлении, во время переправы через реку Стугну, на его глазах утонул его родной брат Ростислав. Владимир хотел спасти брата, но едва не утонул сам. По словам летописца, он вернулся в Чернигов «печален зело», с остатками дружины, «мнози бо падоша от полка его, и боляре его ту падоша».
Нашествия 1093 года и трех последующих лет стали самыми страшными в истории домонгольской Руси. После долгой осады половцам удалось взять город Торческ — важную крепость на реке Роси, населенную в основном торками, подвластными киевскому князю, а также какие-то иные, не названные летописцем города. Полностью разорена была значительная территория, в том числе окрестности Киева; население уведено в плен или перебито. Летописец с горечью писал о бедствиях «христианского рода», рисуя едва ли не апокалиптические картины: «Сотвори бо ся плачь велик в земли нашей, опустеша села наша и городи наши, быхом бегаючи пред врагы нашими». И далее — вызывающее острую жалость описание мучений сотен русских пленников, уведенных в рабство: «Стражюще, печални, мучими зимою, оцепляеми, в алчи, и в жажи, и в беде, опустневше лици, почерневше телесы, незнаемии страною, языком испаленым, нази ходяще и боси ногы имуще сбодены терньем…» Мир с половцами был заключен лишь в следующем году, причем для того, чтобы его добиться, Святополку пришлось взять в жены дочь половецкого хана Тугоркана.
В нашествие 1093 года Чернигов не пострадал. Однако злоключения Владимира еще далеко не закончились. Права на Чернигов предъявил его двоюродный брат и прежний союзник и друг князь Олег Святославич. Чернигов был городом его отца, и Олег не в первый раз пытался захватить его силой, отстаивая свое право на владение «отчиной». Летом 1094 года князь Олег Святославич начал войну за Чернигов, вновь — уже в третий раз за шестнадцать лет — «наведя» на Русь половцев.
И Владимир опять уступил. По его собственным словам, добровольно ушел из Чернигова после восьмидневной осады города: «съжаливъси хрестьяных душъ, и сел горящих, и манастырь». Позднее он образно вспоминал о том, как в самый день памяти горячо почитаемого им святого Бориса (24 июля) с небольшой дружиной, с женами и детьми, вышел из Чернигова и вынужден был ехать сквозь половецкие полки, ожидавшие поживы; «и облизахутся на нас, акы волци… [и] Бог и святыи Борис не да им мене в користь, неврежени доидохом Переяславлю».
Казалось бы, вот еще одно жестокое поражение Мономаха — поражение и военное, и политическое, и моральное. Но, удивительное дело, в итоге Владимир выиграет, а не проиграет. Признав отчинные права Олега на Чернигов, он укрепился в Переяславле — городе, в котором ему предстояло княжить в течение девятнадцати лет, до перехода на княжение в Киев в 1113 году. Главное же заключалось в том, что он уступил не силе (хотя и силе тоже), но праву, и тем самым избавился от возможных упреков в несправедливом владении тем или иным княжеским столом. Именно эта его моральная безупречность и сделает его в определенном смысле неуязвимым в политическом отношении и принесет ему вполне ощутимые дивиденды.
Первые годы переяславского княжения Владимира Мономаха оказались особенно трудными из-за голода и постоянных половецких нападений. После стугнинской катастрофы и гибели брата Владимир, кажется, изменил свое отношение к половцам и стал сторонником более решительных действий против них. Переломным стало событие, произошедшее в феврале 1096 года, на второй год его пребывания в Переяславле, когда сюда для мирных переговоров с князем явились два половецких военачальника — Итларь и Кытан. Дружина уговорила князя напасть на половцев и убить их. И вопреки своим первоначальным намерениям, поддавшись на уговоры и подавив голос собственной совести, Владимир решился нарушить им же данное слово. Впрочем, летописец сумел найти весомый аргумент для того, чтобы оправдать князя. «Нету ти в том греха, — передает он слова, обращенные к Владимиру дружиной, — да они всегда к тобе ходяче роте (то есть дав клятву. — А.К.) губять землю Русьскую и кровь хрестьянску проливают бесперестани». Так интересы Русской земли и «христианского рода» перевесили в глазах Владимира все прочие аргументы, в том числе его же крестное целование.
Убийство послов стало прологом к успешному походу на половцев, который Владимир совершил совместно со Святополком в конце февраля — марте 1096 года. Князья выступили за Голтав (город и река в Переяславской земле) и подвергли опустошению половецкие становища (вежи): «и взяста веже, [и] полониша скоты, и коне, вельблуды, и челядь, и приведоста и в землю свою». Это первый отмеченный летописью успех русских после стугнинской катастрофы. По крайней мере три его составляющие будут приносить победы русским князьям и впоследствии, во время русско-половецких войн в XII веке. Это, во-первых, согласованные действия князей, во-вторых, их наступательный, а не оборонительный характер, перенесение войны в Половецкую степь и, в-третьих, удачный выбор времени года для начала похода: как оказалось, именно в конце зимы — весной половецкие вежи были наиболее уязвимы из-за отсутствия кормов для лошадей. Так первый совместный успех Владимира и Святополка предопределил их будущие победы.