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