Действительно, уже 15 марта в Воронеж выступил из Москвы сам «воевода большого полку» Алексей Семенович Шеин, проследив за тем, чтобы все его генералы с полками начали движение к месту сбора. 31 марта, «во втором часу ночи», он был уже в Воронеже.
К этому времени строительство флота в основном завершилось. Два 36-пушечных корабля («Апостол Петр» и «Апостол Павел»), 23 галеры, 4 брандера, 1300 стругов, 300 морских лодок, 100 плотов – это была внушительная сила, способная решить две стратегические задачи: обеспечить перевозку по реке Дон «ратных людей», «наряда» и необходимых военных запасов и, главное, блокировать крепость Азов с моря.
С 1 апреля началась погрузка на струги пушек, пороха, свинца, ядер, бомб, хлебных запасов. Затем на судах распределили солдатские и стрелецкие полки. За этим следил сам генералиссимус Шеин, решая споры между генералами. Он же инспектировал готовую к отплытию «судовую рать». 10 апреля боярин «пришел к Воронежской пристани к берегу на будары (струги.
23 апреля отправился в плаванье генерал Гордон с Бутырским и 2 стрелецкими полками. 25 апреля отбыл генерал Головин с Преображенским, Семеновским и 3 стрелецкими полками. Наконец, 26 апреля двинулся в путь вниз по Дону главнокомандующий. Шеин плыл на струге «чердачном дощатом косящетом с тремя чердаки (каютами.
Второй Азовский поход начался.
Петр I отплыл из Воронежа на галере «Принципиум» 3 мая, о чем тут же сообщил в письме, посланном вдогонку плывущему по Дону боярину Шеину. Впрочем, 12 мая он обогнал струги Шеина и прошел вперед. Царь спешил к устью Дона, чтобы в морских баталиях отогнать турецкий флот и блокировать Азов с моря.
Ранним утром 27 мая русский галерный флот вышел в море и выстроился поперек Таганрогского залива, окончательно блокировав Азов.
Турецкий султан послал на помощь Азову большую эскадру, на которой кроме боеприпасов и продовольствия для осажденных находился 4-тысячный десант янычар, но пройти к Азову ему не удалось.
Иные заботы были у боярина Шеина. Вся махина надвигавшейся на Азов армии лежала на его плечах, а «морские баталии» близ устья Дона были лишь малой частицей войны.
Алексей Семенович Шеин прибыл в Черкасск 19 мая вместе с генералом Головиным, которого нагнал в пути. За 2 версты от города его встретил наказной атаман Илья Зернщиков со знатными донскими казаками. В Черкасске Шеину как главнокомандующему представился генерал-майор Ригеман. 2 из 3 командиров дивизий, таким образом, прибыли на место. Генералы незамедлительно получили приказ выступать к Азову. Это был первый боевой приказ генералиссимуса: «Устроясь обозом, воинским ополчением итти под Азов сухим путем со всяким бережением, а пришед к Азову, стать обозом в тех же местах, где стояли в прошлом году московских войск ратные люди, и под Азовом промысел чинить, сколько милосердный бог помощи подаст, смотря по тамошнему делу».
В придонских степях по-прежнему господствовала крымская конница, и опытный воевода предписывал использовать ту же организацию марша, которая оправдала себя в Крымских походах: двигаться большими каре, в окружении обозных телег, чтобы обеспечить безопасность людей от возможных нападений конницы. С той же целью генералам предписывалось и под Азовом «стать обозом», т. е. в укрепленных лагерях. Ни на какие активные действия до полного сосредоточения армии у Азова генералиссимус своих генералов не подталкивал. Они должны были «промысел чинить», только «смотря по тамошнему делу».
Воевода сохранял лучшие традиции русского военного искусства XVII столетия: осмотрительность, последовательность, тщательную подготовку каждого действия, внимание к укреплениям – и на марше, и на стоянках. Горячим петровским генералам пришлось приноравливаться к требованиям опытного воеводы, облеченного высшей воинской властью…
Ушел из Черкасска генерал Ригеман со своими полками, полки дивизии Головина (сам генерал оставался пока в городе), донские казаки и калмыки под начальством атамана Савинова. Прибыл в Черкасск адмирал Лефорт.
Наконец, Шеин известил письмом царя: «Я пошел от Черкаского в надлежащий путь сего жь числа. Слуга вашей милости Алешка Шеин. Майя 24 день».