23 апреля отправился в плаванье генерал Гордон с Бутырским и двумя стрелецкими полками. 25 апреля отбыл генерал Головин с Преображенским, Семеновским и тремя стрелецкими полками. Наконец, 26 апреля двинулся в путь вниз по Дону главнокомандующий. Шеин плыл на струге «чердачном дощатом косящетом с тремя чердаки (каютами) и с чуланы»; еще девять стругов было выделено для его людей, поварни и запасов. Генералиссимуса сопровождал только его штаб, а «полков с ним никаких не было».
Второй Азовский поход начался.
Петр I отплыл из Воронежа на галере «Принципиум» 3 мая, о чем тут же сообщил в письме, посланном вдогонку плывущему по Дону боярину Шеину. Впрочем, 12 мая он обогнал струги Шеина и прошел вперед. Царь спешил к устью Дона, чтобы в морских баталиях отогнать турецкий флот и блокировать Азов с моря.
О том, что там произошло, лучше всего, пожалуй, поведал сам царь в письме к А. А. Виниусу от 31 мая 1696 года:
«Сего месяца в 15 день приехали мы в Черкаской и стояли два дня; и собрався с галерами, посадя людей, пошли в 18 числе к каланчам в 9 галерах и пришли того же дни часу во 2 ночи к каланчам. И наутрея по шли на море, при чем и казаков было несколько лодок; и той ночи и утрее за малиной устья пройтить было невозможно, потому что ветер был северной и воду всю в море сбил; однако ж, увидев неприятельских судов, в мелких судах на море вышли. А неприятель из кораблей, которых было 13, выгружеся в 13 тунбас (грузовое судно), для которых в провожанье было 11 ушколов (вооруженная лодка), и как неприятель поровнялся с Каланчинским устем, и наши на них ударили и помощию Божиею оныя суды розбили, из которых 10 тунбасов взяли и из тех 9 сожгли; а корабли, то видя, 11 ушли, а 2 — один утопили сами, и то без всякого запасу. На тех тунбасах взято: 300 бомб великих, пудов по пяти, 500 копий, 5000 гранат, 86 бочек пороху, 26 языков и много всякого припасу: муки, пшена, уксусу ренского, бекмесу, масла деревянного, а больше сукон и рухляди многое число; и все, что к ним на жалованье и на сиденье прислано, все нашим в руки досталось. Петр С моря, майя 31 дня».
Ранним утром 27 мая русский галерный флот вышел в море и выстроился поперек Таганрогского залива окончательно блокировав Азов.
Чтобы больше не возвращаться к военным действиям на море, следует сказать, что турецкий султан послал на помощь Азову большую эскадру, на которой, кроме боеприпасов и продовольствия для осажденных, находился четырехтысячный десант янычар, способных значительно усилить гарнизон осажденной крепости. Но пройти к Азову турецкому десанту не удалось. 23 июня 1696 года Петр писал в Москву князю Ф. Ю. Ромодановскому: «Доношу, что сего месяца 14 дня прислан к Азову на помочь Анатолский Турночи баша с флотом, в котором обретаются 3 каторги, 6 кораблей, 14 фуркатов да несколько мелких судов, который намерен был в Азов пройтить; но, увидя нас, холопей наших, принужден был намерение свое отставить; и стоит вышепомянутый баша в виду от нашего каравана и смотрит, что под городом делается». 28 июня турецкий адмирал приказал поднять паруса, и эскадра окончательно ушла из-под Азова…
Иные заботы были у боярина Шеина. Вся махина надвигавшейся на Азов армии лежала на его плечах, а «морские баталии» близ устья Дона были лишь малой частицей войны.
Алексей Семенович Шеин прибыл в Черкасск 19 мая вместе с генералом Головиным, которого нагнал в пути. За две версты от города его встретил наказной атаман Илья Зернщиков со знатными донскими казаками. В Черкасске Шеину, как главнокомандующему, представился генерал-майор Ригеман. Два из трех командиров дивизий, таким образом, прибыли на место. Генералы незамедлительно получили приказ выступать к Азову. Это был первый боевой приказ генералиссимуса: «Устроясь обозом, воинским ополчением итти под Азов сухим путем со всяким бережением, а пришед к Азову, стать обозом в тех же местах, где стояли в прошлом году московских войск ратные люди, и под Азовом промысел чинить, сколько милосердный бог помощи подаст, смотря по тамошнему делу».
В придонских степях по-прежнему господствовала крымская конница, и опытный воевода предписывал использовать ту же организацию марша, которая оправдала себя в Крымских походах: двигаться большими каре, в окружении обозных телег, чтобы обеспечить безопасность людей от возможных нападений конницы. С той же целью генералам предписывалось и под Азовом «стать обозом», то есть в укрепленных лагерях. Ни на какие активные действия до полного сосредоточения армии у Азова генералиссимус своих генералов не подталкивал. Они должны были «промысел чинить», только «смотря по тамошнему делу».