Через два года, в 1071 году, Всеслав, во главе войска из варягов, литовцев, эстов, семигалов стоял под Полоцком – «выгнал Всеслав Святополка из Полоцка». Изяслав с войском послал своего сына Ярополка вернуть Полоцк, но сил хватило только на один бой, недалеко от Минска. Войска разошлись по домам. Всеслав вновь вокняжился в Полоцке и стал укреплять и приводить в порядок земли. За четыре года киевские наместники сильно разорили и Полоцк и Полоцкую землю. Историк В. М. Игнатовский писал:
«Усердно работал князь над улучшением Полоцкой земли, охранял ее от натиска соседей, и нападая на соседние, особенно киевские, земли. Не знал он за всю свою долгую жизнь, что такое свободное время и отдых. Откуда только взялось столько политического разума, хитрости и неиссякаемой энергии у этого труженика древней старины? Этот вопрос интересовал и современников Всеслава. Современники не могли этого понять и не могли согласиться с тем, что это обычный, простой человек, как все. Разве может простой человек иметь такую энергию, мощь и быстроту? Народ был уверен в том, что Всеслав имеет необычную силу, что он колдун, чародей, что он, например, может рыскать серым волком через сотни верст. Ходило среди народа предание, что и родился он от волшебства. Своим умом, своим непокорным, сильным духом князь-волшебник надолго остался в народной памяти».
В 1073 году Всеслав участвовал в конфликте триумвиров. К нему с предложениями о союзе обращались и Изяслав Киевский, и Святослав Черниговский. Триумвират распался, «Изяслав же пошел в ляхи с добром многим и с женой, надеясь на богатство великое и говорил: «Этим найду я воинов». Он даже сумел на короткое время через несколько лет занять киевский стол, но почти тут же погиб – в 1078 году. Киевом с 1073 по 1076 год правил ставший великим киевским князем Святослав Ярославич.
Пять лет мирной жизни полностью использовал Всеслав Вещий – его Полоцк, его земля расцветала и хорошела с каждым годом. Современный белорусский историк А. А. Марцинович писал в работе «Зерно к зерну», вышедшей в Минске в 1996 году:
«С силой Всеслава уже не могли не считаться, как и не могли не признавать его власть. Дань ему платили даже предки современных латышей. Породниться с полоцким князем за честь считал византийский император, взявши в жены его дочку. Со всех концов приезжали в город на Полоте купцы. Их привлекало гостеприимство здешних людей, их состоятельность, что в торговле очень важно, поскольку всегда найдутся потенциальные покупатели. Да и сам князь любил встречаться с торговцами, поговорить с ними о жизни, просил привозить больше товаров. Не забывал и про книги.
Само управление в княжестве происходило, используя современные термины, демократическим путем. Князь стоял во главе войска, однако воевать или не воевать, решало городское вече. Вообще, оно имело немалые по тем временам права. Давало разрешение на войну или отказывало в ведении боевых действий. Вече могло спросить у князя, почему он проиграл битву. Интересовалось оно и какой ценой одержана победа. Если большой и дорогой, выясняло, почему… Вече посылало посольства в другие страны, решало многочисленные проблемы повседневной жизни».
Мирная жизнь Полоцкого княжества закончилось в 1076 году. Всеволод Ярославич, ставший великим киевским князем, и его сын, черниговский и смоленский князь Владимир Мономах, объединив военные силы чуть ли не всей Южной Руси, двинулись на Полоцкое княжество. Историк П. Г. Чигринов писал:
«В течение нескольких лет Всеслав, стремясь ограждать свои земли от притязаний со стороны киевских князей, всемерно укреплял могущество Полоцкого княжества. С конца 70-х годов XI века в борьбу с полоцкими князьями включился Владимир Мономах, тогдашний князь черниговский и смоленский, что придало этой борьбе исключительно напряженный и жестокий характер. Много раз под руководством Владимира Мономаха соединялись южнорусские князья, чтобы подчинить центральной, великокняжеской власти полоцкие земли.
Ярославичи стремились любыми средствами обескровить, ослабить Полотчину. Этому способствовал тот факт, что отец Владимира Мономаха, Всеволод, занял в то время киевский престол и этим самым «переемь всю власть русскую», в Новгороде «сидел» Святополк Изяславич – давний враг Всеслава Полоцкого. Как видно, Полоцкое княжество оказалось почти в окружении».
После смерти Святослава Ярославича опять началась стихшая было резня за княжеские столы. Его сыновьям – Роман Святославич княжил в Тмутаракани, а Олег Святославич на Волыни – их дядя Всеволод Ярославич предложил отдать свои столы. Олегу Святославичу, например, было предложено уехать в маленькое Муромское княжество. Все недовольные князья собрались в Тмутаракани, пока Всеволод пытался забрать их родовые земли. Недовольных князей поддержал Всеслав Чародей. Именно поэтому Владимир Мономах в 1077 году попытался взять Полоцк – ему это не удалось. Он, как обычно, разграбил округу. В 1078 году Владимир Всеволодович решил кончать с Полоцким княжеством, впервые в славянской истории позвав в поход извечных врагов Киевской Руси и всего Древнерусского государства – половцев. Однако даже с насильниками, столько лет уничтожавшими мирное население, Мономаха опять постигла неудача – воинское искусство Всеслава и мужество полочан свели на нет весь «союзнический» поход. В. Чаропка писал:
«С Плоцком срочно нужно было кончать. Владимир Мономах собирает громадное войско, какого со времен Святослава Игоревича не было на Руси. Все военные силы Южной Руси, новгородская дружина князя Святополка (которого некогда Всеслав выгнал из Полоцка) и половецкая орда зимой 1078 года пошли на Полоцк. Когда-то с такой силой Олег принудил Византию к покорности, повесил свой щит на ворота Константинополя. Наверно, Мономах тешил себя надеждой, что Полоцк доживает последние дни своей независимости. Однако и на этот раз оказались бессильными против Полоцка Мономаховы рати. Снова Всеслав оборонил столицу своей державы. В гневе Мономах сжег полоцкие предместья, а возвращаясь домой в Чернигов, камня на камне не оставил от Одрска. Этот город так и не возродился к жизни. За такой жестокостью пряталось бессилие Киева. Годы борьбы с непокорным Всеславом не принесли желанной победы. Змей, который был готов проглотить Полотчину, обломал на ней свои зубы».
Весной 1078 года недовольные Святославичи и союзные им князья пошли в поход на Чернигов, владения Мономаха. В сентябре 1078 года в бою на реке Соже они разбили киевские и черниговские войска во главе с Всеволодом Ярославичем. В Чернигове стал княжить Олег Святославич, Мономаху остался Смоленск. С. В. Тарасов писал:
