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