Родился ок. 1029. Сын князя Брячислава Изяславича Полоцкого. Правнук Владимира Святославича и Рогнеды.

Всеслав занял Полоцкое княжество в 1044 после смерти своего отца. Вопреки политике отца, Всеслав первое время княжения жил в согласии с Ярославичами и в 1060 участвовал вместе с ними в походе на торков.

С 1065 Всеслав начал набеги на соседние княжества, разграбив окрестности Киева, затем совершил набег на Псков, который продержал в осаде, но не взял, а в 1067 на берегу р. Черехи он разбил войско новгородского князя Мстислава Изяславича и занял Новгород, который наполовину был сожжён. Всеслав захватил пленных, снял с новгородского Софийского собора колокола и прихватил к себе в княжество иконы и утварь новгородских церквей.

В начале 1067 Всеслав захватил Новогрудок. Но в том же году против него выступили совместно трое Ярославичей: Изяслав Киевский, Святослав Черниговский и Всеволод Переяславский. В битве на Немиге 3.03.1067 Всеслав потерпел поражение, а спустя четыре месяца в районе Орши был обманом, под предлогом мирных переговоров, захвачен в плен и приведён в Киев, где его и двоих его сыновей посадили в поруб

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

Изяслав посадил князем в Полоцке своего сына Мстислава (вскоре умершего и заменённого его братом, Святополком).

Всеслав бежал к води, набрал из неё войско и 23.10.1069 появился у Новгорода, но опять был разбит.

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

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

Когда братья Изяслава, Святослав и Всеволод, изгнали Изяслава из Киева, они при этом не тронули Всеслава. Но в 1077-1078 борьба Всеслава с Ярославичами возобновилась. В 1083 сын Всеволода Владимир Мономах совершил поход на Полоцк и сжёг предместья города. За это Всеслав в том же году подступил к Смоленску и до прихода Владимира Мономаха успел зажечь город и уйти.

Всеслав Брячиславич умер в 1101 и после его смерти Полоцкое княжество разделилось на несколько уделов. Он последний держал в одних руках всю полоцкую землю, пережившую под его властью время расцвета своих сил (он правил в Полоцке 57 лет). Популярный в своём княжестве, он пользовался большой славой и за его пределами. Князь Всеслав упомянут в "Слове о полку Игореве", где он предстаёт как богатырь и волхв (колдун, чародей).

При нём в Полоцке в 1066 был воздвигнут кафедральный собор Св. Софии, который, как и одноимённая церковь в Чернигове, явился символом амбиций Полоцка, притязаний на равенство со столичным Киевом. Колокола собора были привезены Всеславом из разграбленного Новгорода, где были сняты с новгородского Софийского собора.

Всеслав умер в 1101 и после его смерти Полоцкое княжество разделилось на 6 или 7 уделов. У него было шесть сыновей: Борис (до 1054-1128), князь Полоцкий (1101-1128), Давыд (ок.1057-после 1129), князь Полоцкий (1128-1129), Глеб (ум. 1119), князь Минский (1101-1119), Роман (ум. 1114/1116), Святослав, князь Витебский, и Ростислав (ок.1070-после 1129), вероятно князь Лукомский (1101-1129).

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

Всеслав Брячиславич известен как герой "Слова о полку Игореве", в котором описывается захват Всеславом Новгорода и битва на Немиге. В "Слове" он предстаёт как богатырь и колдун (волколак), активно ищущим киевского великокняжеского стола, тогда как, по летописи, он оказался на нём скорее помимо воли. Личность Всеслава и события киевского восстания 1068 года отразились в былине "Вольх Всеславьевич".