Собравшись возле Белой церкви с достаточными силами, Хмельницкий выступил с ними на расправу с врагами в конце января 1656 года. Заставы их в округе Смелянском, где они прятались от холода по селам и хуторам, атаковал их со всей жестокостью, не давая им объединиться, гнал от села к селу, совершая повсеместно над ними кару. Для этого распределены были у него войска на много деташементов с резервами и легкой артиллерией, а посередине их подкреплял и наступал сам гетман со своими силами. Убегая, враги собрались и остановились возле местечка Межибожа, решив дать битву Хмельницкому. Но гетман, наступая на них пехотой и смешанной конницей, разбил все их соединения, потому что войска вражеские, которые состояли почти все из конницы, из-за глубокого снега плохо могли действовать, а сагайдаки татарские в сильные морозы и вовсе нельзя было использовать. К тому же казацкие войска своим оружием и пушечной стрельбой непрерывно их поражали и за несколько часов заставили бежать с потерями. На месте побоища убито до 30 тысяч человек. Убегая, враги разделились на две части: поляки ушли опять в Молдавию и оттуда пробрались внутрь Польши, а татары потянулись степями в Крым. Взятые ими у поляков за поход талеры обернулись им гибелью, ибо они преодолевали широкие степи глубокими снегами, и твердый наст поранил и привел к гибели всех лошадей, сами же татары едва тащились пешком до своих аулов, потеряв много людей замерзшими и засыпанными снегами. А гетман, по той же причине, прекратил за ними погоню.
Весной, объединившись с боярином Бутурлиным, Хмельницкий начал поход с объединенными войсками вовнутрь Польши, чтобы опередить и не дать возможности польским войскам соединиться с турецкими и татарскими. Осуществляя этот поход до Бродов, Львова и Замостя, они овладели этими городами при слабом сопротивлении. Польские войска, не смея показываться им в поле, придерживались городов и замков, и при приближении к ним российских войск, при первых же с ними перестрелках, они везде были разбиты и рассеяны за пределы городов, которые они бросали со всеми запасами в пользу победителей. Горожане еще хорошо помнили о победах Хмельницкого, его великодушии и милости к ним. Поэтому выходили из городов и встречали российские войска с мирными предложениями и молитвами, жертвуя при этом для войск легкой помощью. Их оставляли в покое без каких-либо военных контрибуций и притеснений, а только описывалось и отбиралось на пользу Государя все, что принадлежало казне Речи Посполитой Польской, и вводились в городские замки русские гарнизоны.