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