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