Олег бежал в дальние края с мыслью силой вернуть себе черниговскую отчину. Его старший брат, тмутороканский князь Роман, не проявил интереса к этой авантюре, быть может полагая, что черниговский стол должен принадлежать ему самому (во всяком случае, впоследствии он сделает попытку им овладеть). Зато планы Олега встретили полное понимание со стороны другого изгоя, с некоторых пор обретавшегося на попечении Романа Святославича, – Бориса, сына смоленского князя Вячеслава Ярославича, умершего в 1058 г. (см. с. 16). Летопись ничего не говорит о том, что он делал все эти годы. Известно только, что 4 мая 1077 г. Борис, воспользовавшись уходом Всеволода навстречу Изяславу на Волынь, внезапно захватил Чернигов, однако продержался в городе всего восемь дней и бежал в Тмуторокань, видимо изгнанный самими черниговцами. И вот теперь, встретившись в Тмуторокани, Олег и Борис договорились о совместных действиях против Всеволода.
Не рассчитывая на собственные дружины, по всей видимости немногочисленные, племянники-изгои заручились поддержкой половецких ханов. В конце лета 1078 г. Олег и Борис «приведоша половци на Русскую землю, и поидоша на Всеволода к Чернигову». Всеволод выступил навстречу им к внешней линии «Змиевых валов». Из Смоленска на выручку отцу шел Владимир Мономах, но смоленские полки не поспели вовремя. 25 августа на реке Сожице (приток Сулы) произошло кровопролитное сражение, в котором войско Всеволода было наголову разбито, потеряно множество простых воинов и знатных людей184. Победители вступили в Чернигов, «мнящеся [что] одолевши», а половцы «земли Рустей много зла сотворивше», как отмечает летопись. Владимир Мономах рассказывает в «Поучении», что по дороге в Переяславль, где укрылся Всеволод, ему пришлось пробиваться «сквозе половечьскыи вой».
Оставив Переяславль на попечение сына, Всеволод бросился в Киев искать помощи у старшего брата. Летописец особо подчеркивает дружественный прием, оказанный ему Изяславом, и вкладывает в уста последнему удивительные слова, которые если и были произнесены в действительности, то прозвучали в княжеском семействе, пожалуй, впервые: «И рече Изяслав ему: «брате! не тужи, видел еси, колико ся зла мне соключи: первое [во-первых] не выгнаша ли мене людие мои