Украйна не хотела быть наследием Лещинского; одни только запорожцы пошли вслед Мазепы. В Запорожье благодаря Каменному Затону нагорела вражда к Москве; вражда эта могла быть потушена не обещанием лишнего жалованья, а срытием Каменного Затона и самарских крепостей, чего не мог сделать царь в угоду козакам. Мы видели грамоту, которую Петр послал в Запорожье после измены Мазепы. Грамоту повезли стольники Кисленский и Теплицкий, вместе с грамотою повезли деньги - 12000 рублей на войско, 500 червонных кошевому, старшине 2000 рублей; с стольниками поехал от нового гетмана лубенский сотник Савич; для увещаний от имени митрополита и всего духовенства отправился иеромонах Иродион Жураковский. Такое торжественное посольство было принято вовсе не торжественно: взявши деньги, запорожцы начали бесчестить посланников, одного из них хотели посадить в воду, иеромонаха называли шпионом и хвалились сжечь его в смоляной бочке; в ответной грамоте не пощадили и царя, требовали, чтоб в малороссийских городах полковников не было, была бы вольница, как в Сечи, чтоб по рекам Пселу и Ворскле мельницы и Переволоченский перевоз были в запорожском владении, чтоб самарским городам и Каменному Затону не быть. Скоро после того перехвачена была грамота запорожцев к Мазепе; низовое войско просило, чтоб присланы были к нам на кош уполномоченные от короля шведского и польского и от него, Мазепы, для заключения договоров, за кем им быть, а для разорения Каменного Затона чтоб присланы были войска, и как только эта крепость будет разорена, запорожцы поспешат к шведам на помощь против московских войск. Бунчужный товарищ Черняк, отправленный Скоропадским к крымскому хану для извещения об избрании нового гетмана, был задержан в Сечи: на раде кошевой Гордеенко бил его до полусмерти и отослал к Мазепе. Чигиринский сотник Невенчанный убил посланного к нему от гетмана Скоропадского и ушел в Запорожье.
В начале 1709 года запорожцы куда-то начали собираться. 20 января царь писал из Сум к Меншикову: "Вчерашнего дня получили мы подлинную ведомость, что запорожцы конные пришли уже давно и кошевого ждут с пехотою вскоре, а сей сбор их только 5 верст от Богородицкого, и опасно, чтоб чего над оным не учинили, также дабы воровством кошевого и судьи не заведены были чрез Переволочну близь шведов (как и Мазепа сделал): того ради зело потребно, дабы Ингерманландский полк в удобном месте поставить и на сей их поход око иметь; также, буде возможно, в Богородицкой людей прибавить". Гетман Скоропадский советовал постараться, чтоб как-нибудь сменить подозрительного кошевого, и Петр написал 18 февраля Меншикову из Воронежа: "Что о запорожцах надлежит, и то гетман советует, чтоб переменить кошевого: и то зело добро, и всегда мы то говорили, что надобно, и, как оное сделать, того способу искать надлежит, которое мню чрез бы миргородского (Апостола) и деньги могло статься; к тому ж неотложно извольте полка два или больши, взяв из гварнизонов, послать в Каменный Затон с добрым командиром". Царь приказывал не жалеть денег для свержения кошевого, "хотя б и не малое что дать". Написали к Апостолу, чтоб выбрал из своего полка добрых козаков и, удовольствовав их, послал в Запорожье в разные курени: пусть там постараются свергнуть кошевого и судью и во всех противниках диверсию учинить. Отправлены были в Сечь с деньгами козаки, бывшие прежде кошевыми, чтоб объявили публично в раде и по всем куреням, что кошевой и судья присягнули Мазепе за деньги. После измены Мазепы Палей был возвращен из Сибири и жил в Москве; теперь придумали, что не лучше ли его привезти в Севск или в другие ближайшие к Украйне места, "понеже оный в таких легкомысленных имеет любовь и не малый кредит". Петр все еще надеялся, что можно подействовать на запорожцев увещаниями, и потому писал Меншикову из Воронежа 1 марта, чтоб над полками, посылаемыми в Каменный Затон, "учинить командира из бригадиров кто поумнее, ибо там не все шпагою, но и ртом действовать надлежит, а кого, то полагаюсь на вас; пункты посылаю при сем, токмо едина материя суть, чтоб смотреть и учинить запорожцев добром по самой крайней возможности; буде же оные явно себя покажут противными и добром сладить будет невозможно, то делать с оными, яко с изменниками".
Исполнилось второе. 11 марта кошевой с 1000 запорожцев и девятью пушками явился у Переволочны и дал знать о своем приходе тамошнему полковнику Нестулею; Нестулей приехал с 500 конных козаков для рады. 1 числа приехали от Мазепы с письмами Чуткеевич и Мокеевич, и 13 числа созвана была рада: читали письма Мазепы, в которых старый гетман объявлял, что царь хочет весь народ малороссийский загнать за Волгу, что московские войска разоряют Украйну пуще шведа. Раздались крики: "Быть на Мазепиной стороне!" - и полковник Нестулей и все запорожцы объявили себя на стороне Мазепы. Положено было действовать против царских войск. Кошевой напал нечаянно ночью на русский отряд, стоявший в местечке Царичевке, был отражен с уроном, но успел захватить в плен несколько русских солдат и с торжеством привел их к королю, стоявшему тогда в местечке Будищах. Известие об этом сильно встревожило Петра в Воронеже; он писал Меншикову 4 марта: "Запорожцы, а паче дьявол кошевой уже явный вор, и зело опасно Богородицкого, не для города, а для артиллерии и аммуниции, которой зело много, а людей мало. Того ради зело потребно, дабы один конный полк послать в Богородицкий, велеть бы оному там побыть, пока из Киева три полка будут в Каменный Затон, из которых велеть сот пять водою отправить в Богородицкой на перемену сему конному".