Из Переяславля братья послали гонцов с речами в Чернигов. Вот как писал об этом, впоследствии в русской летописи черноризец Нестор: «И послали Святополк с Владимиром к Олегу, говоря: «Бот ты не пошёл с нами на поганых, которые разорили землю Русскую, а держишь у себя Итларевича — либо убей его, либо отдай нам. Он враг наш и Русской земли». Олег же того не послушал, ж стала между ними вражда».

Олег не ответил на послание братьев, но Святополк ж Владимир не успели наказать его за отказ от помощи — вновь вышли из степи половцы. На этот раз это были не приднепровские, а дальние причерноморские куманы, которые решили взять с русских земель свою долю добычи. Они прорвались через русские укреплённые городки и валы, вышли к реке Роси, осадили город Юрьев, и уже здесь их нашли гонцы Святополка, предложив мир и откуп. Половцы поначалу согласились, но, взяв откуп, нарушили мир и вновь осадили Юрьев. Ночью юрьевцы, боясь плена и гибели, оставили город и ушли в Киев, а наутро половцы вошли в Юрьев и сожгли его, забрав оставшееся имущество. Снова началась изнурительная борьба, снова князья собирали рать и гонялись за врагом, и становилось ясно, что без объединения всех русских сил, без начала большого наступления на половецкое поле невозможно было остановить эти бесконечные выходы, эти постоянные грабежи, пожоги, от-купы, которые обескровливали Русь, отнимали у неё многие силы.

Возвратившись в Переяславль после ухода причерноморских половцев, Мономах всё чаще и чаще стал задумываться о том, как Русъ должна дальше строить свою борьбу с извечным врагом — половцами, вспоминал свой неожиданный победоносный поход к половецким вежам и всё больше и больше склонялся к мысли, что не оборона, не отсиживание за крепостными стенами и валами, не гонка за половецкой конницей до необозримым просторам принесёт желанный успех, а лишь постоянное, мощное, хорошо подготовленное движение в степь всех наличных общерусских сил.

Всё чаще он говорил об этом Святополку и в Переяелавле и в степи, когда они гонялись за половцами.

Святополк слушал Мономаха, думал о своём, но не спорил: он давно, уже после Стугны, признал полное военное превосходство Владимира и теперь лишь делал вид, что он обдумывает какие-то решения, и целиком полагался на опыт Мономаха.

А Владимир уже пришёл к твёрдой мысли, что нужен общерусский съезд князей, который заставил бы и Олега с братьями Давыдом и Ярославом, и Ростиславичей, и Давида Игоревича взять на свои общие плечи дело обороны Русской земли, и, конечно, Владимир думал, что именно он вместе со Святополком поведёт эту общую русскую рать в глубину половецкой степи, чтобы воевать с половцами на их земле, среди их кибиток, шатров, городков. Наступала осень 1095 года. По-прежнему неспокойно было на Руси. В Чернигове, окружённый верными ему половцами, сидел Олег. Давыд Святославич попытался вернуть себе Новгород, но новгородские мужи встали за Мстислава, Мономахова сына, и послали навстречу Давыд у гонцов, и те сказали ему: «Не ходи к нам». И Давыд возвратился в Смоленск.

Вышел из ростовских лесов второй сын Мономаха — Изяслав Владимирович. Упоенный победами отца над половцами, окончательным утверждением брата в Новгороде и отступлением Давыда, юный Изяслав прошёл с дружиной по волостям Святославичей.

Не сумев вернуть Смоленск, он обрушился на северскую землю, захватил сначала Курск, а оттуда прошёл в лесной Муром, который всегда тянул к Ростову и Суздалю и недавно в обход лествицы был захвачен Олегом Святославичем. Изяслав выбил из Мурома Олегова посадника ж вновь воссоединил муромский стол с ростово-суздальской землёй.

Мономах, узнав об этом, не очень удивился. Он увидел в действиях Изяслава опытную и решительную руку Ставки Гордятича. Как бы там ни было, но сыновья ведут себя как настоящие князья, как воины и опять стягивают в прочный кулак обширные Всеволодовы волости. Теперь весь Северо-Восток был снова в руках Мономаха и его сыновей.

Это укрепление своей собственной власти, умножение своих богатств и земель Мономах решил использовать для большого наступления на степь.

Каждый князь чувствовал себя временным жильцом в любом городе, пока половцы свободно гуляют по Русской земле. Он уже несколько раз говорил об этом Святополку, и наконец, братья согласились начать большой разговор об устроении Русской земли, о прекращении зависти и междоусобиц.

Вначале решили обратиться к Олегу. Братья послали к нему новых гонцов с предложением прийти в Киев и положить поряд о Русской земле перед епископами, игуменами, боярами, горожанами о том, как сообща оборонить Русскую землю от половцев.

Олег ответил дерзко и высокомерно: «Не вместно меня судить епископам, игуменам или смердам». Гонцы братьев привезли Олегу новые речи Святополка и Владимира: «Это ты потому ни на поганых не ходишь, ни на совет к нам, что злоумышляешь против нас и поганым хочешь помогать, — пусть бог рассудит нас».

Всю осень и зиму шли переговоры Святополка и Владимира с Олегом, и лишь тогда, когда стало ясно, что Олег лишь ждёт случая для расправы с двоюродными братьями, объединённое киевско-переяславское войско двинулось да Чернигов.

В пути к братьям присоединился Давыд Игоревич, пришедший по их зову с Волыни.

Теперь, кажется, все хотели свести с Олегом счёты. Святополк стремился сломить соперника, который, как он знал, в любой час может выгнать его из Киева, как когда-то сделал это отец Олега с его отцом; Давыд мстил за изгон его из Тмутаракани. Мономах не мог забыть своего унижения под Черниговом, когда он покидал город, сломленный и обезлюдевший, после страшного поражения на Стугпе, а половцы усмехались, глядя на него и его детей. И всё это сделал Олег, продавший Русскую землю половцам за власть над Черниговом.

Глухое раздражение поднималось в душе Мономаха, вспоминавшего свой позорный отъезд из Чернигова. Олег становился для него главным врагом, врагом беспощадным, на всю жизнь. Никогда ранее Владимир не испытывал в душе таких чувств, но никогда ранее никто не повергал его в такое смятение. Что бы там ни было, но Олег должен быть сокрушён.

Олег, не уверенный в черниговцах, многие из которых не могли ему простить дружбы с половцами, помощь Итлареву сыну, разорения с согласия князя степняками' черниговских земель, выбежал с дружиной в Стародуб — сильную крепость, которая не раз выдерживала длительные осады. В Чернигове же оставил воеводу с небольшим войском.

В Стародубе обступили братья Олега. Было это в начале мая 1096 года.

Первые приступы стародубцы отбили, и началась долгая осада крепости. Святополк и Владимир переняли все пути в Стародуб, оставили город без ествы, отрезали от сёл и деревень. Горожане пока питались старыми запасами, приканчивали домашний скот, кур, но и эта ества быстро таяла.

Вскоре братья устроили ещё один приступ, и снова стародубцы отбились.

На исходе второй недели осады Святополк предложил спалить город при помощи деревянных башен, подвезённых к городу и зажжённых около самых крепостных стен, а также путём забрасывания в город стрел со смоляными горящими наконечниками. Братья долго спорили по этому поводу. Мономах противился предложению Святополка. Он говорил, что спалить город, конечно, можно, но при этом погибнет много невинных людей, мирных христиан, женщин и детей. Святополк же, стремясь во что бы то ни стало одолеть Олега и желая сберечь своих дружинников, которых у него было не так уж много, настаивал на своём.

В конце концов решили лишь попугать осаждённых огнём, продолжать плотную осаду и постараться сокрушить город голодом.

Тридцать три дня стояли Святополк, Владимир, Давыд Игоревич и сыновец Святополка Ярослав Ярополчич около Стародуба, а на тридцать четвёртый день горожане запросили пощады. Они пришли к Олегу, попросили у него прощения и сказали, чтобы он мирился с братьями, потому что они, горожане, более такого утеснения и голода не перенесут.

Молча выслушал Олег горожан и не ответил им. Приступ означал бы гибель для города, который победители разнесут на куски, возьмут людей в полон, вынесут всё из домов. Как может он после этого вновь появиться в Стародубе, а жизнь была ещё долгой, и кто знает, не нужен ли будет ему этот город впредь в борьбе с братьями. Приступ мог бы означать гибель или плен и самого Олега, а следом за Стародубом откроет неприятелям ворота и Чернигов, и иные, тянущие к нему города, и тогда снова изгойство, метания по дальним весям и градам.