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