Ростислав сел в Тмутаракани крепко и подобно Мстиславу Владимировичу, брату и сопернику Ярослава, брал дань с касогов, и не с них одних. Это не могло устроить греков. Сильный русский князь на берегу Черного моря их пугал. На пиру подосланный убийца отравил Ростислава, 3 февраля князь скончался. А грека, подсыпавшего в княжеский кубок яд, побили камнями в Корсуни.
В 1067 г. началось новое противостояние Киева и Полоцка. Князь Всеслав Брячиславович «заратисяс» подобно отцу и деду. И вновь жертвой полочан стал Новгород.
Как только весть о том достигла Киева, Изяслав, Святослав и Всеволод, собрав силы, зимой выступили к Старому Меньску, располагавшемуся к юго-западу от современного Минска. Город взяли штурмом, мужчин посекли, а жен и детей полонили.
После того Ярославовичи двинулись на север, к реке Немиге. Тут южнорусские полки ожидала рать Всеслава. В день битвы, 3 марта, снег был глубок. Это стесняло движения полков, и начавшаяся битва была жестокой. На Немиге пало множество воинов. В конце концов Всеслав бежал.
Ярославовичи не удовольствовались победой на Немиге. В июне Изяслав и Всеслав целовали крест к Всеславу и просили прийти для переговоров к Орше на Днепр и заверяли «не створи зла». Всеслав переехал Днепр в ладье и вошел в шатер к Изяславу. И «яша Всеслава на Рши оу Смоленьска преступивше крестъ». Изяслав «всадил» Всеслава с двумя сыновьями «в поруб» в Киеве. Но на этом история с полоцким князем не закончилась.
В 1068 г. на Русь снова пришли половцы. Изяслав, Святослав и Всеволод с дружинами стали на реке Л то. И разыгралась трагедия. Летописец сообщает, что русские князья «поидоша противу собе, грехъ ради нашихъ». Это можно понять как несогласованность действий полков, то, что впоследствии сгубило русское войско в битве с монголами на реке Калка. И среди ночи «попусти Богъ на ны поганыя». И побежали русские воины. Изяслав и Всеволод направили коней к Киеву. Святослав помчался к Чернигову.
Узнав черную весть, киевляне, а было их в ту пору не менее пятидесяти тысяч, собрали на торговище вече. Послали к князю просить коней и оружие — сражаться с половцами. Среди жителей столицы было немало людей, владевших усадьбами и дворами, стоявшими за валами города, и с присутствием половцев в русских землях никто мириться не желал. Когда Изяслав требуемого не дал, народ стал роптать на княжеского воеводу Косняча. Пришли на гору, ко двору воеводы, но Косняч заблаговременно исчез.
Тогда киевляне стали у двора покойного полоцкого князя Брячислава (отца Всеслава), имевшего собственную резиденцию в Киеве, и решили высадить из поруба Всеслава Полоцкого и его дружину. Часть народа устремилась к погребу, а часть, пройдя мост, отправилась на княжеский двор, в город Владимира.
Изяслав, сидя «на сенехъ» в окружении дружины, с тревогой наблюдал за запрудившим двор народом. Киевляне «начаша претися съ княземь». Князь глядел в окно и ожидал совета от своего окружения и «ре Тукы, Чюдине брат, Изяславу — видиша княже людье вьзвыли, поели ать блюдуть Всеслава».
Тем временем киевляне освободили Всеслава, и весть о том мгновенно облетела Киев. Время Изяславом было упущено. Дружина еще советовала Изяславу «се зло есть поели ко Всеславу, ать призвавше ко оконьцю и проньзнути и мечемь, и не послуша сего князь». А киевляне стекались к порубу, окружая Всеслава.
Изяслав и брат его Всеволод сели на коней и, хорошенько их пришпорив, помчались прочь из Киева.
Киевляне кинулись на опустевший княжеский двор и принялись грабить «бещисленое множьство злато и сребра, и кунами и скарою».
Изяслав, нигде подолгу не задерживаясь, скакал в Польшу, ко двору Болеслава II. Польша в ту пору была сильна и надежды Изяслава в дальнейшем оправдала.
Пока в сентябре в Киеве неистовствовали восставшие половцы, жгли на Руси все, к чему могли подобраться, и полонили не успевших укрыться в городах людей.
Наконец, Святослав вывел из Чернигова три тысячи воинов и подошел к городу Сновску. Тут русские увидели превосходивших их численно в несколько раз половцев. Святослав промолвил дружине: «потягнемь». Началось сражение, и русские одолели. Часть половцев перебили, часть перетопили в реке Сновь. Это было 1 ноября 1068 г.
А Всеслав Полоцкий сел в Киеве, и продлилось его княжение в столице семь месяцев.
Весной 1069 г. к Киеву из Польши шли войско Болеслава II и дружина Изяслава Ярославовича. Бояре и гридьба Изяслава не менее самого князя рвались расквитаться с киевлянами. На Руси у них остались дворы, земли, жены.
Всеслав с киевлянами стал в Белгороде, в западном пригороде столицы. Полоцкий князь с тревогой выслушивал сообщения о приближении неприятеля и в ночь «оутаися Кыанъ, бежа из Белагорода кь Полотьску». Поутру бегство Всеслава открыли, и киевляне вернулись в город. Собрали вече и послали к Святославу и Всеволоду с речью: «Мы же зло створили… князя своего прогнавше, а се ведеть на ны землю лядьскую, и пойдете в град оца своего». Далее киевляне пригрозили Ярославовичам: «Зажегши городъ свои и ступити в Грецискую землю».