Казацкие предводители, Лобода и Наливайко, действовали пока независимо один от другого, и, по объяснению Райнольда Гейденштейна, это происходило вследствие личного нерасположения Наливайко, человека властного и честолюбивого, к Лободе. Отдельно от Лободы действовал и Матвей Саула (иначе Шауля), направившийся с частью запорожских казаков в Литву и Белоруссию для добывания там «хлеба-соли», но он предпринял поход с ведома Лободы и имел целью собрать большие стации для всего запорожского войска.

Видя, до какой смелости дошли казаки и их предводители, польский король Сигизмунд нашел нужным принять, наконец, решительные против них меры: он отправил приказание своим гетманам «рушить против них войско и поступать с ними как с государственными неприятелями». Вместе с этим приказанием король послал, в конце января 1596 года, свой универсал волынской шляхте с извещением об отправлении против казаков коронного войска и с приглашением соединиться с этим войском против общих врагов.

На ту пору коронным гетманом был Ян Замойский, а вольным гетманом – Станислав Жолкевский, оба люди решительные, оба с большими военными дарованиями, но оба занятые в то время окончанием дела в Молдавии, низвержением с престола незаконного правителя ее Розвана и возведением на господарский престол Еремии Могилы. Выезжая в Молдавию, Замойский пока старался о том, чтобы казаки не беспокоили в его тылу турок и потому отдал им такого рода лаконическое приказание: «Приказываю вам, казаки, не смейте беспокоить Турцию! Я вам запрещаю!» Уладив же дела в Молдавии и поставив господаря ее в вассальную зависимость от Польши, Замойский вернулся в Польшу и тут отправил с частью коронного войска против казаков Станислава Жолкевского.

Приказание короля и коронного гетмана Станислав Жолкевский получил 28 февраля и, понимая всю важность казацкого восстания для республики Речи Посполитой и ее шляхетского сословия, немедленно двинулся к Кременцу. Однако, при всей своей энергии и решительности, Жолкевский должен был действовать против врага не столько открытой силой, сколько хитростью и неожиданностью. Дело происходило оттого, что после похода в Молдавию польские войска были сильно изнурены и нуждались в деньгах, которых им, по обыкновению, правительство всегда недоплачивало или же затягивало расплату на неопределенное время. Чтобы подкрепить свое войско и вселить ему бодрость, Жолкевский обращался с посланиями к коронному гетману, а также к киевскому и волынскому воеводам, прося у них вспомоществования деньгами и войсками.

Но на усиленные просьбы Жолкевского гетман и воеводы отвечали слишком медленно.

А между тем Наливайко, услышав о собиравшейся против казаков грозе, нашел за лучшее передвинуться из Волыни в Брацлавщину и расположиться в местечке Лабуне (тепершней Волынской губернии, Заславского уезда), где он считал свое положение более надежным, чем где бы то ни было, потому что здесь находил и большое к себе со стороны простого населения сочувствие и потому что отсюда, как из пограничной области, он мог, в случае надобности, свободнее перескочить в другое место. Расположившись в Лабуне, Наливайко беспечно стал поджидать к себе свою ватагу, разъехавшуюся по дальним окрестностям для собирания добычи и продовольствия.

Разведав обо всем этом и сообразив, как трудно будет выкурить Наливайко из Брацлавщины, Станислав Жолкевский решил, не дожидаясь подкрепления, напасть врасплох на Наливайко, захватить его в руки и тем затушить восстание казаков в самом гнезде. И свой план Жолкевский мог привести в исполнение, если бы в самом войске гетмана не объявился перебежчик к казакам, пан Плоский с целой ротой поляков. Не получив давно ожидаемого королевского жалованья, Плоский внезапно покинул Жолкевского, перешел к Наливайко и предупредил его об опасности. Тогда Наливайко оставил Лабун и направился в имение князя Острожского Острополь. Во время этого передвижения в имении князя Радзивилла, Марцирицах, между Лабуном и Острополем, на две сотни войска Наливайко, предводимые Дурным и Татаринцем, напал передовой отряд Жолкевского и вступил с ними в ожесточенный бой. Казаки только что выпили у марцирицкого арендатора целую бочку горилки и потому не совсем были годны для сражения, но тем не менее, засев во дворах и хатах села Марцириц, они оказали такое упорное сопротивление польским жолнерам, что те, не могши одолеть их оружием, решили за лучшее поджечь огнем казаков в их убежищах и тем истребить всех до единого. Казаки не струсили перед опасностью и, поражая поляков из пламени, все, числом до 500 человек, вместе с двумя своими сотниками, погибли в огне, оставив полякам в добычу лишь одни знамена, но ни одного пленника из своих товарищей.

Сам предводитель казацкий, Наливайко, не дойдя до Острополя, остановился в селе Чорнаве, имея при себе вначале, как сообщали о том князю Острожскому, всего лишь несколько десятков казаков. Но потом он успел стянуть к себе из соседних селений все свои отряды и стал с ними в Чорнаве чатами (то есть разъездами на перекрестках). Жолнеры, в числе трех хоругвей, снова незаметно подкрались к казакам, но, убив у них 30 человек в Чорнаве, ничего больше не могли им сделать, а только заставили их двинуться к Острополю. У Наливайко было теперь несколько более тысячи человек казаков, с которыми он всю ночь уходил от жолнеров, направляясь через Острополь в Пиков и не останавливаясь нигде ни днем ни ночью. Поляки по пятам преследовали казаков, но, дойдя до селения Райкова, у самого Острополя, Жолкевский принужден был дать отдых своему истомленному быстрыми переходами войску и переночевать там.

Захватив здесь живыми шесть человек казаков, Жолкевский пустился по направлению к Пикову и пришел сюда только двумя часами позже, чем вышел из Пикова Наливайко. Наливайко взял направление к Брацлаву и шел, по словам самих польских писателей, в большом порядке (sprawa wielka), имея при себе 20 гармат, много гакивниц, еще больше того пороху, ядер и пуль и приковав к пушкам пушкарей для того, чтобы всегда иметь их при войске. В Пикове Жолкевский узнал, что Наливайко, прежде чем решиться двинуться в Брацлав, отправил туда посланца с просьбой о подкреплении, и потому польский вождь решил не допустить казаков до Брацлава. Оставив лишний багаж, Жолкевский ускорил свою погоню за казаками и настиг их над речкой Олыпанкой. Тут произошла незначительная перестрелка между жолнерами и казаками, но густой лес и наступившая ночь не дали им вступить в решительное столкновение друг с другом. У Бельского и Гейденштейна, рассказывающих об этом событии, мы находим противоречивые показания: один говорит, что между казаками и поляками дошло дело до сражения, другой говорит, что сражения, вследствие наступившей ночи, не было. Отсюда Наливайко, не дождавшись ответа из Брацлава, оттого впавши в сомнение относительно верности к нему жителей этого города, нашел за лучшее взять направление в дикие поля к речке Синие Воды, впадающей в реку Буг. Но Жолкевский не переставал гнаться за Наливайко и преследовал его до тех пор, пока у польского вождя не стало коней. Однако, дойдя до Синих Вод, Жолкевский остановился в «уманском лесу» и, боясь безводных, диких и голодных степей, решил прекратить свою погоню за казаками. Райнольд Гейденштейн, рассказывая об этом событии, говорит, что причиной остановки Жолкевского был недостаток у него запасов и фургонов, а также искалечение, от быстрых переходов, полковых лошадей и неимение в дикой степи никаких селений, в которых можно было бы найти все необходимое для войска.