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