В первые годы своего правления Всеслав был союзником сыновей киевского князя Ярослава (Изяслава, Святослава, Всеволода). Так, в 1060 году Ярославичи вместе с полоцким князем совершили удачный поход на торков – тюркоязычных кочевников, обитавших в причерноморских степях.

Однако в 1065 году Всеслав неожиданно напал на Псков, а в следующем году – на Новгород. Последний был взят и разграблен, Всеслав снял даже колокола с главной новгородской святыни – Софийского собора (возможно, они были нужны для только что построенного собора Святой Софии в Полоцке). Этими действиями Всеслав, по словам летописца, «начал междоусобную войну».

Зимой 1067 года великий киевский князь Изяслав и его братья, черниговский князь Святослав и переяславский князь Всеволод, двинулись на Полотчину. Первым полоцким городом, который оказался на их пути, был Минск. Жители Минска, очевидно ожидая скорого прихода Всеслава с войском, решили обороняться «затворишася вь градѣ». Однако минчане не смогли устоять против войск великого князя и его братьев.

Всеслав, узнав, что Минск находится в руках Ярославичей, поспешил на помощь. Битва произошла 3 марта 1067 года на Немиге – небольшой речке, истоки которой находились в районе современной Грушевки в Минске. «И была сеча жестокая, – записал летописец, – и многие пали в ней, и одолели Изяслав, Святослав и Всеволод, Всеслав же бежал».

Следует отметить, что лучшие люди Руси того времени относились к междоусобицам русских князей крайне отрицательно. В «Слове о полку Игореве», написанном неизвестным автором предположительно в конце XII века, подчёркивается братоубийственный характер битвы Ярославичей с Всеславом: «На Немиге снопы стелют головами, молотят цепами булатными, на току жизнь кладут, веют душу от тела. У Немиги кровавые берега не добром были посеяны – посеяны костьми русских сынов». Как видим, все павшие на поле брани воины – и полочане, и киевляне, и черниговцы, и переяславцы – были для автора «русскими сынами», представителями одного народа. Призывая южнорусских и западнорусских князей прекратить братоубийственную вражду, автор «Слова» восклицает: «Вы бо своими крамолами начясте наводити поганыя на землю Русьскую, на жизнь Всеславлю!» Под «жизнью Всеславлю» автор понимал владения полоцкого князя Всеслава, которые мыслились как часть «земли Русской».

Летопись не рассказывает, что было дальше, после взятия Минска и победы Ярославичей над Всеславом. Неизвестно, разъехались ли южнорусские князья по домам или остались на Полотчине. Что стало с Всеславом и Полоцком? Ничего об этом неизвестно. Известно лишь, что противостояние продолжилось летом.

Повесть временных лет сообщает, что в том же году южнорусские князья стояли лагерем под Оршей. Ярославичи не желали вступать в битву с полочанами, а потому попросили Всеслава, который стоял с войском на другом берегу Днепра, переплыть к ним в шатёр для переговоров, поклявшись путём крестоцелования, что ничего с ним не сделают. Всеслав, взяв с собой двух сыновей, исполнил просьбу своих двоюродных дядей, после чего был вероломно схвачен и увезён в Киев, где его вместе с сыновьями заточили в тюрьму.

На следующий год Ярославичи потерпели жестокое поражение от половцев на реке Альте. Когда весть об этом достигла Киева, киевляне потребовали от своего князя Изяслава выдать им оружие и коней для борьбы с половцами. Перепуганный князь колебался. Тогда низы двинулись к темнице, где томился Всеслав, взломали стены и освободили его. Узнав об этом, Изяслав бежал за помощью в Польшу к своему родственнику – королю Болеславу. 15 сентября 1068 года восставшие киевские низы, вопреки правилу престолонаследия, провозгласили великим князем Всеслава. Таким образом представитель полоцкой ветви Рюриковичей всё-таки занял великокняжеский престол, несмотря на то, что не имел на это законных оснований.

Всеслав княжил в Киеве семь с половиной месяцев. Об этом периоде его деятельности летописи хранят полное молчание. Можно предположить, что всё связанное с пребыванием Всеслава на великокняжеском престоле, было изъято при редактировании летописей по требованию последующих киевских князей.

По этой причине большой интерес представляют сведения о Всеславе, почерпнутые из «Слова о полку Игореве», хоть они и облечены в образную поэтическую форму: «Всеслав князь людей судил, князьям города рядил, а сам в ночь волком рыскал: из Киева дорыскивал до петухов в Тмутаракань». В словах «Всеслав князь людей судил» историки видят намёк на какие-то реформы, проведённые князем в сфере судопроизводства. Реформы могли касаться прежде всего «людей», т. е. простого люда. Это нововведение, возможно, заключалось в том, что князь сам осуществлял судопроизводство, не передоверяя его тиунам. Выражение «из Киева дорыскивал до петухов в Тмутаракань» рассматривается как указание на организованный Всеславом поход в далёкую Тмутаракань на Таманском полуострове.

Пропустив период правления Всеслава в Киеве, автор Повести временных лет сразу переходит к рассказу о возвращении прежнего князя, Изяслава. Возвращался он не один, а с польским войском короля Болеслава. Киевляне приготовились к бою, расположившись лагерем под Белгородом. Видя превосходящие силы противника, Всеслав проявил малодушие – оставил киевское войско и под покровом ночи сбежал в Полоцк.

В 1916 году великий русский писатель и поэт Иван Бунин напишет стихотворение, в котором изобразит князя Всеслава тоскующим по киевскому престолу:

Князь Всеслав в железы был закован,

В яму брошен братскою рукой:

Князю был жестокий уготован

Жребий, по жестокости людской.

Русь, его призвав к великой чести,

В Киев из темницы извела.

Да не в час он сел на княжьем месте:

Лишь копьём дотронулся Стола.

Что ж теперь, дорогами глухими,

Воровскими в Полоцк убежав,

Что теперь, вдали от мира, в схиме,

Вспоминает тёмный князь Всеслав?

Только звон твой утренний, София,

Только голос Киева! – Долга

Ночь зимою в Полоцке… Другие

Избы в нём, и церкви, и снега…

Далеко до света, – чуть сереют

Мёрзлые окошечки… Но вот

Слышит князь: опять зовут и млеют

Звоны как бы ангельских высот!

В Полоцке звонят, а он иное

Слышит в тонкой грёзе… Что года

Горестей, изгнанья! Неземное

Сердцем он запомнил навсегда.

Вернуться в Киев Всеславу не довелось. Более того, великий киевский князь Изяслав, движимый уязвлённым самолюбием, организовал поход на Полоцк и изгнал оттуда Всеслава, посадив на полоцкий стол своего сына Мстислава, а когда тот умер, на его место сел другой сын великого князя – Святополк. Всеслав же после этого оказался далеко на севере, у финно-угорского племени водь, и оттуда пытался овладеть Новгородом, однако потерпел поражение и попал к новгородцам в плен. Оказавшись вскоре на свободе, он вновь собрал войско и в 1071 году изгнал из Полоцка Святополка.