Брячислав умер в 1043 году, и на его место заступил сын Всеслав, знаменитейший из князей полоцких. Предание говорит, что мать его родила от волхвованья. На голове у него оказалась язва, и волхвы велели матери обвязать голову, а ему носить эту повязку до самой смерти, «которую и носит Всеслав, говорит летописец под 1043 годом, до сего дне на себе сего ради не милостив есть на кровопролитье».
С 1064 года Всеслав начал воевать. По следам отца ходил он (1067) на Новгород и ограбил город.
«Всеслав разшибе славу Ярослав(л)ю, скочи волком до Немигы с Дудуток».
Ярославичи пошли на него за то войной, взяли Минск, иссекли мужей, а жен и детей взяли на щит.
На Немизе, 3 марта 1067 года, «была сеча злая, говорит летопись, и многие пали».
Певец Слова о полку Игореве описывает сечу так: «на Немизе снопы стелют головами, молотят чепи харалужными, на тоце (на току) живот кладут, веют душу от тела. Немизе кровави брезе не бологом (не благом) бяхуть посеяни, посеяни костьми Руськых сынов».
Ярославичи потом обманом уговорили Всеслава переправиться к ним через Днепр, поцеловав крест, что не сделают ему зла. 10 июля, когда он приплыл к ним в ладье, они захватили его на Рши у Смоленска и отослали в Киев. Там посажен он был в темницу с двумя сыновьями.
На следующий год (1067) в Киеве, среди народного мятежа, вследствие отказа великого князя Изяслава вновь идти на половцев, дружина советовала великому князю убить Всеслава, но тот не согласился, — Всеслав, освобожденный, посажен на стол (13 сентября).
Когда Изяслав воротился с польской помощью через семь месяцев (1068), Всеслав вышел к нему навстречу, но тайком от киевлян бежал ночью из Белгорода в Полоцк. «Скочи от них лютым зверем в полночи из Белаграда, обесися сине мгле (обвернувшись синею мглою)».
Изяслав прогнал его и оттуда и посадил сына своего Мстислава, который вскоре там умер, замещенный Святополком (1069).