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