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