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