Тогда уже, как видно, выработался вполне характер Владимира и в нем созрела мысль действовать не для личных своих выгод, а для пользы всей русской земли, насколько он мог понимать ее пользу; главное же - энергически соединенными силами избавить русскую землю от половцев. До сих пор мы видели, что Владимир, насколько было возможно, старался устроить мир между русскими и половцами, но с этих пор он становится постоянным и непримиримым врагом половцев, воюет против них, подвигает на них всех русских князей и с ними все силы русских земель. Вражду эту он открыл поступком с двумя половецкими князьями: Китаном и Итларем. Князья эти прибыли к Переяславлю договариваться о мире, разумеется, с намерением нарушить этот мир, как делалось прежде. Китан стал между валами за городом, а Итларь с знатнейшими лицами приехал в город: с русской стороны отправился к половцам заложником сын Владимира Святослав.
Тогда же прибыл от Святополка киевлянин Славята и стал советовать убить Итларя, приехавшего к русским. Владимир сначала не решался на такое вероломство, но к Славяте пристали дружинники Владимира и говорили: "Нет греха в том, что мы нарушим клятву, потому что сами они дают клятву, а потом губят русскую землю и проливают христианскую кровь".
Славята с русскими молодцами взялся проникнуть в половецкий стан за городом и вывести оттуда Мономахова сына Святослава, посланного к половцам заложником. С ним вместе взялись за это дело торки (народ того же племени, к которому принадлежали и половцы, но, будучи поселены на киевской земле, они верно служили Руси). В ночь 24 февраля они не только счастливо освободили Святослава, но умертвили Китана и перебили его людей.
Итларь находился тогда во дворе у боярина Ратибора; поутру 24 февраля Итларя с его дружиною пригласили завтракать к Владимиру; но только что половцы вошли в избу, куда их позвали, как за ними затворили двери, и сын Ратиборов Ольбег перестрелял их сверху через отверстие, сделанное в потолке избы. После такого вероломного поступка, который русские оправдывали тем, что их враги были так же вероломны, Владимир начал созывать князей против половцев, и в том числе Олега, от которого потребовал выдачи сына убитого Итларя. Олег не выдал его и не шел к князьям.
Киевский князь Святополк и Владимир звали Олега в Киев на совет об обороне русской земли. "Иди в Киев, - говорили ему князья, - здесь мы положим поряд о русской земле пред епископами, игуменами, перед мужами отцов наших и перед городскими людьми, как нам оборонять русскую землю". Но Олег высокомерно ответил: "Не пристало судить меня епископам, игуменам и смердам" (т. е. мужичью, переводя на наш способ выражения).
Тогда князья, пригласившие Олега, послали ему от себя такое слово: "Если ты не идешь на неверных и не приходишь на совет к нам, то, значит, ты мыслишь на нас худое и хочешь помогать поганым. Пусть Бог нас рассудит".
Это было объявление войны. Итак, вместо того чтобы идти соединенными силами на половцев, Владимиру приходилось идти войною на своих. Владимир со Святополком выгнали Олега из Чернигова, осадили его в Стародубе и держали в осаде до тех пор, пока Олег не попросил мира. Ему даровали мир, но с условием, чтоб он непременно прибыл в Киев на совет. "Киев, - говорили князья, - старейший город на русской земле; там надлежит нам сойтись и положить поряд". Обе стороны целовали крест. Это было в мае 1096 года.
Между тем раздраженные половцы делали на Русь набеги. Хан половецкий Боняк со своею ордою жег окрестности Киева, а тесть Святополка Тугоркан, несмотря на родство с киевским князем, осадил Переяславль. Владимир со Святополком разбили его 19 мая; сам Тугоркан пал в битве, и его зять Святополк привез тело тестя в Киев: его похоронили между двумя дорогами: одною, ведущею в Берестово, и другою - в Печерский монастырь. В июле Боняк повторил свое нападение и 20 числа утром ворвался в Печерский монастырь. Монахи, отстояв заутреню, почивали в кельях; половцы выломали ворота, ходили по кельям, брали что попадалось под руки, сожгли церковные южные и северные двери, вошли в церковь, таскали из нее иконы и произносили оскорбительные слова над христианским Богом и законом. Тогда половцы сожгли загородный княжеский двор, называемый красным, построенный Всеволодом на выдубичском холме, где впоследствии выстроен был Выдубицкий монастырь.
Олег не думал исполнять договора и являться в Киев на княжеский съезд. Вместо того он явился в Смоленск (где тогда неизвестно каким путем сел брат его Давид), набрал там войска и, вышедши оттуда, пошел вниз по Оке, ударил на Муром, который достался в управление сыну Мономаха Изяславу, посаженному на княжение в соседней ростовской земле. (Отец Олега Святослав, сидя в Чернигове, был в то же время на княжении и в Муроме, и потому Олег считал Муром своею отчиною). 6 сентября 1096 года Изяслав был убит в сече. Олег взял Муром и оковал всех найденных там ростовцев, 6елозерцев и суздальцев: видно, что князь Изяслав управлял муромцами при помощи людей своей земли. В Муроме и его волости в то время еще господствовало язычество; край был населен народом финского племени, муромою, и держался за князьями только посредством дружины, составлявшей здесь, вероятно, еще единственное славянское население в те времена. В Ростове, Суздале и Белозерске, напротив, славяно-русская стихия уже прежде пустила свои корни, и эти края имели свое местное русское население.
Олег, отвоевавши Муром, взял Суздаль и поступил сурово с его жителями: одних взял в плен, других разослал по своим городам и отнял их имущество. Ростов сдался Олегу сам. Возгордившись успехами, Олег затевал подчинить своей власти и Новгород, где на княжении был другой сын Мономаха Мстислав, молодой князь, очень любимый новгородцами. Новгородцы предупредили покушение Олега и, прежде чем он мог встать с войском на новгородской земле, сами отправились на него на ростовско-суздальскую землю. Олег убежал из Суздаля, приказав в досаде сжечь за собою город, и остановился в Муроме. Мстислав удовлетворился тем, что выгнал Олега из ростовско-суздальской земли, которая никогда не была уделом ни Олега, ни его отца; предложил Олегу мир и предоставлял ему снестись со своим отцом. Мстислава располагало к уступчивости то, что Олег был его крестным отцом. Олег притворно согласился, а сам думал внезапно напасть на своего крестника; но новгородцы узнали об его намерении заблаговременно и вместе с ростовцами и белозерцами приготовились к бою. Враги встретились друг с другом на реке Колакше в 1096 году. Олег увидел у противников распущенное знамя Владимира Мономаха, подумал, что сам Владимир Мономах пришел с большою силою на помощь сыну, и убежал. Мстислав с новгородцами и ростовцами пошел по его следам, взял Муром и Рязань, мирно обошелся с муромцами и рязанцами, освободил людей ростовско-суздальской области, которых Олег держал в городах Муроме и Рязани пленниками; после того Мстислав послал к своему сопернику такое слово: "Не бегай более, пошли с мольбой к своей братьи; они тебя не лишат русской земли". Олег обещал сделать так, как предлагал ему победитель.
Мономах дружелюбно обошелся со своим соперником, и памятником тогдашних отношений его к Олегу осталось современное письмо его к Олегу, очень любопытное не только потому, что оно во многом объясняет личность князя Владимира Мономаха, но и потому, что вообще оно составляет один из немногих образчиков тогдашнего способа выражения: "Меня, - пишет он, - принудил написать к тебе сын мой, которого ты крестил и который теперь недалеко от тебя: он прислал ко мне мужа своего и грамоту и говорит так: сладимся и примиримся, а братцу моему суд пришел; не будем ему мстителями; возложим все на Бога; пусть они станут пред Богом, мы же русской земли не погубим. Я послушался и написал; примешь ли ты мое писание с добром или с поруганием, покажет ответ твой. Отчего, когда убили мое и твое дитя перед тобою, увидавши кровь его и тело его, увянувшее подобно едва распустившемуся цветку, отчего, стоя над ним, не вник ты в помыслы души своей и не сказал: зачем это я сделал? Зачем ради кривды этого мечтательного света причинил себе грех, а отцу и матери слезы? Тебе было бы тогда покаяться Богу, а ко мне написать утешительное письмо и прислать сноху мою ко мне... она тебе не сделала ни добра, ни зла; я бы с нею оплакал мужа ее и свадьбу их вместо свадебных песен. Я не видел прежде их радости, ни их венчания; отпусти ее как можно скорее, я поплачу с нею заодно и посажу на месте, как грустную горлицу на сухом дереве, а сам утешусь о Боге. Так было и при отцах наших. Суд пришел ему от Бога, а не от тебя! Если бы ты, взявши Муром, не трогал Ростова, а прислал бы ко мне, мы бы уладились; рассуди сам, тебе ли следовало послать ко мне или мне к тебе? Если пришлешь ко мне посла или попа и грамоту свою напишешь с правдою, то и волость свою возьмешь, и сердце наше обратится к тебе, и будем жить лучше, чем прежде; я тебе не враг, не мститель".