Прогнанием татар из Украины не окончились военные действия против бусурман; напротив, они только что начинались в более важном размере. У царя Петра созрело твердое намерение завоевать у турок Азов и создать русское мореплавание на Азовском и Черном морях. Малороссийский гетман прилагал соответственное старание к ведению этого предприятия, чрезвычайно важного и смелого по своему времени. Мазепа подавал совет послать для охранения Таванска великороссийских ратных людей, а запорожцев отправить в чайках[76] на море для разрыва неприятельских сил, которые, конечно, будут отправлены турками в судах на выручку Азова. Для этого, по его соображениям, необходимо было прислать 1000 рублей на сооружение запорожской флотилии из чаек и две тысячи четей[77] хлебных запасов на 2000 человек запорожцев, которые отправятся в море на три месяца; следовало, кроме того, устроить флотилию для плавного похода войск по Днепру. Суда для этого гетман находил удобным делать в Брянске и оттуда Десною спустить в Днепр. Правительство отправило гетману требуемую сумму на постройку запорожских чаек, а относительно плавного похода заметило, что если суда в Брянске не поспеют, то гетман тогда должен сам найти еще иные способы приготовления судов к плавному походу вместе с Шереметевым. Вслед за тем царский посол Бухвостов привез гетману указ отправить 15000 конницы и 5000 пехоты казацкого войска под Азов, давши им на пять месяцев запасов. Гетман отвечал, что хотя он готов и сам лично вести козацкий отряд под Азов, но должен доложить, что в малороссийском крае едва ли наберется такое число Козаков с лошадьми, какое требуется; большая часть козачества, за недостатком лошадей, может вступить в бой пешими, и разве только у начальных лиц и у значных товарищей будут свои боевые кони. Он может набрать всего, и конных и пеших, тысяч пятнадцать для отправления под Азов. Он считает возможным взять запасов только на три месяца: их придется везти гужом, а водяного пути нет. На это представление 2 апреля 1696 года дан был ответ, что дозволяется взять козакам, снаряжаемым под Азов, запасов на три месяца, но с тем, что на остальные два месяца запасы будут доставлены водою по Северному Донцу, который становится судоходным начиная от Белгорода. Кроме того, указано было купить в Слободской Украине 500 волов и 1500 баранов и, по распоряжению Шереметева, отправить на Дон.
24 апреля отправил гетман требуемый царем под Азов козацкий отряд в числе 15 000 человек под наказным гетманством Якова Лизогуба, черниговского полковника, бывшего когда-то наказным гетманом Дорошенка на правой стороне Днепра. С ним пошли два городовых полка — Гадяцкий и Лубенский, два полка охотных — один конный, другой пеший, и один компанейский. Путь их лежал на Ахтырку и Валуйки. За ними вслед велел гетман везти запасы на телегах на три месяца и сверх того каждому козаку приказано взять с собою денег для покупки себе продовольствия еще на один месяц. Гетман в своем донесении в приказ заметил, что доставить запасы на два месяца до Северного Донца для дальнейшей сплавки по воде очень затруднительно: люди посполитые обнищали от неприятельских разорении, от кормления охотных войск, от запорожских проездов и не могут снарядить достаточного числа подвод; многие ушли уже в слободские полки для переселения. До сих пор посполитые возили подводы с запасами только охотным козакам, компанейцам и сердюкам, а городовые козаки всегда возили себе запасы сами на своих лошадях; теперь же из городовых многие так обеднели, что, отправившись в поход, не оставили при своих семьях никакой челяди, которая бы могла везти их запас; некоторые едва могли взять с собой для прокормления что-нибудь на дорогу и сами выступали в поход на единственном коне, на котором дома работали.
25 апреля последовал царский указ Шереметеву, по совету с гетманом, идти плавным походом под Очаков или в другое место с 2500 ратных в больших стругах, изготовленных в Брянске и спущенных через Десну в Днепр; сверх того гетман должен был распорядиться о постройке судов в городах гетманского регимента и приказал гнать их Днепром до Переволочны или до устья Орели.
В Запорожской Сече, еще не дождавшись от гетмана денег, присланных царем на постройку запорожских судов, в апреле снарядился и отправился в море на чайках атаман Чалый с 500 сечевиков. Тогда кошевой Гусак домогался, чтобы гетман выдал ему присланные царем для постройки чаек деньги, извещая, что, кроме ушедших уже в море с Чалым, собираются еще охотники туда же, но отправить их из Сечи не на чем. Гетман отвечал, что не даст ни денег, ни запасов, пока не убедится в действительной охоте запорожцев идти на царскую службу.