Строительство судов для похода под Очаков началось и в Украине. На собственные средства, безусловно, желая отличиться перед влюбленным в море царем, Мазепа построил 50 судов. Остальные старшины и казаки изготовили 70 морских стругов и 600 лодок. Всю зиму завозили необходимые боеприпасы и продовольствие запорожцам. В мае войска вплавь выступили по Днепру.
Главнокомандующим был белгородский воевода Яков Долгоруков (Шереметев после Кизикирмена был направлен с посольством в Англию). Помимо прочего везли строительные материалы для укрепления Кизикирмена и Таванска. Оставив охрану Украины на попечение Даниила Апостола, Мазепа лично выступил в поход. Русская и украинская армии соединились под Коломаком и уже в начале июля были под Кодаком. Переправа через Днепр далась с трудом. Уровень воды на порогах был в тот период очень низкий, что затрудняло переправу. Немало судов погибло вместе с запасами и людьми. Было потеряно почти десять дней.
Войска были еще у Вольного порога, когда пришло известие от боярина Шеина, что тот, восстановив и укрепив Азов, оставил там гарнизон и направился в пределы Московского государства. Эта новость очень взволновала Мазепу. Он имел сведения от разведки, что крымский хан, выйдя к Каланчаку, намеревался напасть на Гетманщину и Слободскую Украину. В этих условиях отход главных русских сил открывал татарам путь на Левобережье, и оставленный на защиту Апостол явно не мог справиться с возможным вторжением.
Из-под Кизикирмена тоже приходили тревожные вести. Турецко-татарское войско захватило Исламкермен и обстреливало Мубеуреккермен. Мазепа выслал отряд в три тысячи казаков с Лизогубом, которые на стругах устремились в Сечь. Второй отряд во главе с Обидовским был направлен сушей по правому берегу Днепра. Сам Мазепа с Долгоруким на стругах с основными силами двигались водным путем. Запорожцы с кошевым Яковенко к тому времени уже подплыли к Таванску. Почти одновременно с ними под Кизикирменом появились Лизогуб и Обидовский. Увидев приближение столь крупных сил, татары оставили Исламкермен и бежали в степь.
Прибытие Мазепы было встречено кошевым атаманом пальбой из мушкетов, вследствие чего, как писал современник, «помрачился воздух, хотя и солнце светило», и долго еще над Днепром стоял туман[352].
Воспользовавшись передышкой, связанной с бегством татар, командиры приняли решение взорвать Мубеуреккермен, так как укрепить его было невозможно. Зато в Кизикирмене и Таванске немедленно приступили к фортификационным работам, которые возглавил немецкий инженер. В частности, был заложен новый обширный таванский город. Тем временем запорожцы расположились южнее Кизикирмена, Обидовский — возле него, а Мазепа и Долгоруков — у Таванска.
На военном совете обсуждался план вытупления в Черное море. Однако разведка донесла о нахождении поблизости турецкого флота, что делало такое предприятие невозможным.
Через несколько дней подошли орда, хан, а также Али-паша с обозом, пушками и отрядами янычар. Немедленно начался штурм Мубеуреккермена, продолжавшийся три дня. Белгородская орда султана Кази-Гирея ударила на Таванск и Кизикирмен. Как писал Мазепа Апостолу, «в кровавом бою находимся». Обстрел велся из ручного оружия и пушек, причем обе стороны несли сильный урон. Огромные усилия белгородская орда направила против табора Обидовского. Понеся тяжелые потери, он со своими людьми был вынужден перейти в основной казацкий лагерь.
Укрепление крепостей было практически закончено, когда 10 августа кошевой атаман с низовья Кизикирмена сообщил, что турецкий флот вошел в устье Днепра.
Мазепа выслал приказ Лубенскому и Гадячскому полкам немедленно поспешить на помощь. Ночью украинско-русское войско на стругах отошло от берега, а утром показался турецкий флот и сразу же начал обстрел из 30 пушек. Бой длился пять дней. Не прекращая перестрелки, денно и нощно казаки завершали укрепление крепостей. Мазепа с Долгоруким лично руководили работами. В результате был построен новый большой таванский городок, с пушками, глубокими и широкими рвами, высокими каменными стенами. Гарнизон был пополнен российской пехотой, отрядом запорожцев во главе с кошевым атаманом Яковенко и казаками. В Кизикирмене Мазепа оставил тысячу удальцов во главе с наказным нежинским полковником Левко Шрамченко и сердюцким полковником Лукьяном Шулгой со всеми необходимыми припасами.
После этого гетман с воеводой в ночь на 16 августа отплыли обратно. Мазепа в письме к Петру объяснял это угрозой вторжения в Левобережье. Кроме того, он не располагал достаточными средствами, чтобы давать битву в поле.