Это подтвердил уже второй решительный политический шаг Владимира: он добровольно отдал Чернигов алчно и нагло Олегу Святославичу и отъехал с княгиней (был женат с английской принцессой Гитою, дочерью короля Гаральд, погибшего 1066 года в знаменитой битве при Гастингси, когда Норман завоевали Англию ) и детьми в город своего детства - Переяслава. Драматично описаны Мономахом в «наставления», как он покидал Чернигов, осажденный войском Олега и приведенными им половецькимы ордами: «Вышли мы в Борисов день  с июня  нигова и ехали сквозь полки половецкие, было нас около 100 человек, считая женщин и детей. И половцы олизывались на нас, как волки, стоя у перевоза и на горах, и господь и святой Борис не выдали меня им на пищу, не поврежденными дошли мы до Переяслава ».
Двадцать долгих лет - с 1094 по 1113 год княжил Владимир в Переяславе. Сначала ему было очень тяжело. Кочевников не раз видризувалы город от Русской земли, препятствовали позволенной пищи и вооружение. В конце жизни Мономах вспоминал: «И сидел я в Переяславе три лета и три зимы с женой своей, и многие беды натерпелись мы от войны и голода». Но и в таких крайне неблагоприятных условиях князь остался верен своей политике, которая стала делом его жизни: борьбе с безжалостным и бродящее половецких ханов. Даже голодные и плохо снаряженная дружинники Владимира ходили на половцев за порубижне город Руси и неоднократно побеждали их.
    В «поучения» является красноречиво упоминание: «И до Старо дуба ходили на Олега , потому что перевернулся то до половцев». Сын Святослава был предателем всероссийских интересов: он первым привел половецких ханов на Русь в борьбе с другими русскими князьями, сделав, как считали древнерусские книжники, «Каин грех» . Поэтому Мономах решился-таки выступить против своего родственника. Но даже до нелюди Олега Владимир относился гуманно. Его благородство оказалось в ситуации, которую сейчас принято называть экстремальной. 1096 года в битве с войсками Олега Святославовича возле валов города Муром на Оке погиб сын Владимира - Изяслав. Однако Мономах не думал о мести. Через своего старшего сына - Мстислава он предлагает Олегу мир с тем, чтобы убийца отступил от незаконно захваченных им Суздаль и Муром.
    Однако Олег грубо отверг мирные предложения, пошел войной на Мстислава и потерпел сокрушительный поражение в битве на «Кулачци» , после чего ему пришлось бежать за пределы Руси. И при таких обстоятельствах победитель Мономах предлагает убийцы своего сына вернуться в Русскую землю, прощает его, обещает предоставить княжество, которое принадлежало Олегу за правом наследия, и даже радует. Сохранился этот удивительной силы и благородства письмо Владимира к Олега. Как писал академик Д. С. Лихачева, «письмо Мономаха впечатляет. Я не знаю в мировой истории ничего похожего ».
Современники и последующие поколения должным образом оценили обоих князей. Величественная памятник древнерусской литературы «Слово о Игоре поход» красноречиво описывает позорный вклад Олега, которого с горькой иронией называют

А «старого Владимира», миротворческий дух которого словно витает над русским обществом времен феодальной роздробленности, автор «Слова» вспоминает с большим уважением. Благодаря решающей роли Мономаха в борьбе с наседающим Половецкая степью растет интерес летописцев к этому переяславского, казалось бы провинциального князя. Поэтому в «Повести временных лет» и в других летописях есть подробные сведения о победные походы Руси на половцев, в которых главенствующую роль играл Владимир Всеволодич.
Уже в первый год своего княжения в Переяславе он во главе верной жены заглибився в степь и разбил половецких ханов за рекой Сулою. В следующем году энергичный Переяславский князь объединился с киевским - Святополком. Летописец вспоминает: «Пошли на башне и взяли башни, и захватили скот и лошадей, верблюдов и людей, и привели их к земле своей. И вознегодовали на Олега за то, что не пошел с ними на плохих  ».
Еще большую победу одержал Владимир Всеволодович (опять же в союзе с Святополка Изяславичем) 1096 года. И хотя военные действия союзников осложнялись деликатной обстоятельством: Святополка был женат с дочерью главного половецкой хана Тугоркана, это не помешало столкновение. Нестор эпические повествует: «Пришло Тугоркан, тесть Святополка, до Переяслава З мая и стал около города, а Переяславцы закрылись в городе. Святополка и Владимир пошли на него этой стороной Днепра и пришли к Заруба, и там перешли броды, и не заметили их половцы, и, приготовившись , ушли в город. Святополка же и Владимир пошли вброд через Трубеж к половцев. Владимир же хотел построить полк, они же 4 не послушались и повалили верхом на врага. Увидев это, половцы побежали, а наши погнались за воинами, рубая врагов. И даровал Господь в тот день спасение великое: 19 июля побеждены были иноплеменники, и князя  убили Тугоркана и сына его и других князей; много врагов наших там погибло ».
Летописец-монах, человек средневековья, наивно объясняет победу русичей над половцами «Господа даром». Современном же читателю легко понять, что Мономах обязан успеху своей дружине, конницы, перед которым не устояли легковооружённый, на слабосилих лошадях и недисциплинированными половцы. И в дальнейшем в славных победах Владимира над половцами главную роль будет играть его прекрасно вооруженная, обученная, быстрая, выносливые и мужественная конная жена.
Триумф над кочевниками 1096 затмился ударом другого половецкой сильного хана - Боняка, «нечестивого и шолудивого», как с ненавистью пишет о нем Нестор. Кафир захватил киевские пригороды и розорил Печерский монастырь, центр науки и культуры, сжег «Красный двор» Всеволода - княжеские загородную резиденцию на Выдубецкого горбу. После этих событий в русско-половецкой противоборстве на несколько лет наступило затишье. Однако половцы продолжали шарпаты южные рубежи Руси.