Владимир шел быстро, не задерживаясь в селениях. Любое промедление грозило бедой с половцами. Степняки действовали молниеносно, как сокол, бьющий добычу. Еще вопль православных от их натиска не исчезал в воздухе, а они уже уносились в сторону, волоча незамысловатую сельскую добычу — всякую живность, разное крестьянское имение и тут же, отбежав, останавливались, ощетинивались. Владимир поначалу пытался уговаривать половецкого хана, звал его к себе в хоромы, тот приходил, слушал упреки, сокрушенно тряс головой, но потом войско проходило новое селение, и все повторялось сначала. Так на пути уже по смоленским землям союзники нанесли немалый урон христианам. В одном из богатых сел на самой границе с полоцким княжеством степняки учинили подлинный разгром. Они не только ограбили смердов, выгнали в свой обоз скотину, но и попытались сжечь дома, когда поселяне схватились за вилы, дубины, косы. В это время смоленская дружина Мономаха и сам князь подъехали к селу. Владимир еще не успел понять, что за суета происходит вокруг, а его люди уже бросились в гущу этой суеты, замелькали в воздухе мечи, послышались резкие, гортанные выкрики половцев, начался бой.
Мономах сидел на коне и смотрел, как русская дружина выбивает из домов степняков, рубит их, а те, прячась за плетеными заборами, засыпают руссов тучей стрел. С той стороны села к Мономаху помчались половецкие всадники во главе с ханом. Они подскакали, лошади взмылены, глаза всадников блистают, речь отрывочна, переходит на крик. «Князь, останови своих воинов, зачем бьешь друзей, зачем вступаешься за холопов?» А мечи все мелькали в воздухе, и стрелы летели из-за углов домов и заборов, и уже убитые и раненые имелись с обеих сторон. А Мономах недвижно сидел на коне, скрестив на груди руки в боевых рукавицах, и смотрел как бы сквозь кричавших ему в лицо половецких вождей.
А потом руссы выбили половцев из села, и те, вскочив на коней, умчались в сторону леса, где располагался их обоз. Дымились остатки сгоревших домов, вопили от горя жены погорельцев, дружинники оттаскивали в сторону своих убитых людей.
— Уйдут степняки, князь, — сказал ему тогда старый друг Ставка Гордятич.
— Не уйдут, — ответил тихо Мономах, — пока свое не возьмут в наших землях, не уйдут. Это мы еще видим, где свои, смоленские земли, а где вражьи — полоцкие. Для них же все одно — они пришли сюда за добычей, за полоном. Не уйдут.
С того дня половцы поутихли, но по всему было видно, что они лишь ждут удобного времени, чтобы оторваться от русского войска и пойти по селам и городкам в свое удовольствие.
В урочище, на выходах из полоцкого леса, Мономаха ждал Святополк с новгородцами. Владимир не видал двоюродного брата много лет и теперь, подъехав к Святополку, ужаснулся: перед ним стоял незнакомый, сухой, седоватый человек, с усталым настороженным взглядом.
Братья поздоровались, потом Владимир прошел в шатер к Святополку, и тут же, не тратя лишних слов, братья начали разговор о том, как лучше сокрушить Всеслава. Решили не гоняться за ним по снегам и лесам, а ударить, как в прежние времена, при Ярославичах, по самому Полоцку. К тому же нельзя было и половецкой коннице позволять без устали грабить русские земли, тогда степняки совсем забудут, зачем их звали в Русь.
К Полоцку новгородско-смоленско-половецкое войско подошло в один из дней в середине января, до полудня. Город после войн прошлых лет отстроился, оброс новой дубовой крепостной стеной с башнями и воротами, и теперь полочане вместе со своим князем стояли на высокой стене и молча смотрели на подходящее многочисленное войско.
Новгородско-смоленская рать расположилась на отдых неподалеку от опушки леса. Скоро запылали их костры, сторожи подошли почти вплотную к крепостным воротам, следя за каждым шагом Всеславовой рати. Половцы огородились телегами в чистом поле, тоже зажгли огни, чтобы согреться, приготовить еству.
После полудня Святополк и Владимир приказали начать приступ. По утоптанному уже сторожами снегу с приступными лестницами и крючьями пешцы двинулись бегом к крепостным стенам, прикрываясь от летящих оттуда стрел щитами.
Лестницы поставили быстро, сразу несколько десятков, в разных местах стены так, что их концы не доставали до крепостных стен, а потому полочанам приходилось высовываться из укрытий, нагибаться, чтобы отпихнуть их от стены. Подошедшие следом за пешцами лучники повели обстрел крепостной стены, мешая защитникам города сбросить с его стен облепившие их лестницы.
Владимир послал своих людей к половцам, прося помочь в приступе, но гонцы вернулись ни с чем: половцы отказывались идти на приступ. Тих и недвижим был их стан, огороженный санями, лишь иногда между ними замечалось какое-то шевеление — то половцы подползали к саням, смотрели из-за них за боем.