Остановившись у Синих Вод и видя свою слабость в сравнении с коронным и панским войском, Наливайко пришел к мысли примириться с Жолкевским, испросить прощения у короля и распустить свое войско. С этой целью он избрал себе посредником брацлавского старосту Александра Струся и через него вошел в переговоры с Жолкевским. На предложение Наливайко Жолкевский отвечал полным согласием, но с условием, чтобы он распустил казаков, выдал арматы и прислал полученную от эрцгерцога Максимилиана войсковую хоругвь. В этих условиях Наливайко усмотрел неискренность со стороны Жолкевского и решил продолжать раз начатое дело восстания казаков против поляков.

Однако, не надеясь на собственные силы, к тому же слыша отовсюду упреки за гибель многих людей и потерю пропитания и коней, опасаясь даже за собственную жизнь, Наливайко решил обратиться к старшому запорожских казаков, Григорию Лободе. «Правдоподобнее, что такой с таким легче сойдется, чем отдастся на ласку его королевской милости», – выразился по этому поводу Жолкевский в своем письме к Замойскому.

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

Очевидно, общность интересов и обоюдная опасность со стороны польских войск заставила Лободу забыть неприязнь к Наливайко и действовать заодно с ним против поляков, а уверенность в своем превосходстве как по численности, так и по военному опыту перед польскими хоругвями давала смелость вождю казацкому, как и самим казакам, грозить польской столице Кракову и главе Польской республики, королю.

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

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

В свою очередь и Саула взял свои меры против Ружинского: оставаясь сам в Киеве, он отрядил 3000 человек под начальством полковника Саська с целью разорить имения князя возле Белой Церкви и, если окажется возможным, поймать самого князя возле наволочи. Выйдя из Киева, полковник Сасько добрался до Хвастова и отсюда отправил от себя разведочный отряд против Ружинского. На этот отряд внезапно напал Ружинский и, захватив несколько человек из него в плен возле речки Каменки (в нынешней Киевской губернии, Васильковского уезда), около 50 пленных казнил смертью. Узнав о поступке Ружинского с пленными казаками, Жолкевский нашел приличным выразить ему по этому поводу свое неудовольствие, хотя в то же время находил и извинение в таком поступке князя: «Я, не считая убитых в сражении, уберег свои руки от их крови; я предпочел бы лечить зараженные члены, чем отсекать; впрочем, не диво и князю Ружинскому: всю эту землю, а его в особенности, казаки проняли до живого».

Разбив передовой отряд полковника Саська у Каменки, Ружинский не захотел возвращаться в Паволоч, а направился в Белую Церковь, считая ее удобной в двух отношениях: во-первых, как «недурную» и даже «неприступную» крепость; во-вторых, как место, откуда можно было хорошо оборонять близлежащие собственные имения. Таким образом, 28 марта он успел прибыть и расположиться в городе со своим отрядом. Но в ту же Белую Церковь двинулись и все казаки. На этот раз вместе с Лободой и Саулой успел соединиться, покинув город Корсунь, и Северин Наливайко.

Желая протянуть время и обмануть врагов, Матвей Саула, 27 марта 1597 года, отправил через ксендза к Жолкевскому и Ружинскому письма и в письме к первому выражал свое удивление по поводу гнева «его милости» на неповинных перед ним людей; а второму напоминал его прежнюю совместную с низовыми казаками службу и просил быть посредником в примирении казаков с гетманом Жолкевским, за что обещал верно и постоянно служить польской короне за порогами Днепра и промышлять над исконными врагами святого креста. Однако ксендз, привезший письмо Саулы Ружинскому, раскрыл истинные намерения казаков, и потому казаки ничего не выиграли от своего замысла.

Быстро подвигаясь от Киева и имея под своим знаменем до 8000 человек, казацкие вожди прибыли к Белой Церкви 2 апреля и, по обыкновению, расположились вокруг замка табором. Белая Церковь, как оказалось, действительно представляла собой «недурную крепость, а при хорошем гарнизоне и неприступную»: замок стоял на горе и сильно укреплен был стенами и окопами; крепость сделана была, собственно, не против казаков, а против татар, которые, по выражению польского писателя Сарницкого, точно собаки, постоянно заглядывали в Белую Церковь, что объяснялось топографическим положением этого города, стоявшего на Черном шляхе, по которому татары обыкновенно врывались на Украину за добычей и ясырем.