А подготовка армии к новому походу началась задолго до назначения главнокомандующего. 27 ноября 1696 года в кремлевской церкви Чудова монастыря появился «сын боярский» из Разрядного приказа и «пошел по церкви кричать, чтобы все стольники, стряпчие, дворяне и жильцы шли Верх к сказке. Там на Постельном крыльце дьяк Артемий Возницын прочитал им указ: собираться на царскую службу, запасы готовить и лошадей кормить». По всей стране проходил усиленный набор в солдаты и рейтары, причем в царском селе Преображенском записывали даже крепостных крестьян. Всем полкам было приказано собраться к 20 марта в Валуйках и Тамбове.
Армия, предназначенная для похода на Азов, на этот раз состояла примерно из семидесяти пяти тысяч человек. Подробные сведения о ней имеются в «Описании похода боярина Шеина» (СПб, 1773). Под знамя с «образом Спасовым» становились тридцать солдатских полков (тридцать восемь тысяч восемьсот человек), тринадцать стрелецких полков (девять тысяч пятьсот девяносто семь человек), шесть «малороссийских» полков (пятнадцать тысяч человек), донские пешие и конные казаки (пять тысяч человек), калмыки (три тысячи человек), яицкие казаки и низовые конные стрельцы (пятьсот человек). В армии также находилось около четырех тысяч московских дворян. Из солдатских и стрелецких полков сформировали три дивизии под командованием генералов Головина, Гордона и Ригемана. Три солдатских полка были выделены Лефорту, назначенному адмиралом. Донскими казаками командовал атаман Фрол Минаев, украинскими — наказной атаман черниговский полковник Яков Лизогуб. Так выглядел командный состав армии А. С. Шеина. И, конечно, важную роль играл и в подготовке, и в самом походе царь Петр I, не занимавший официально «генеральской» должности.
Сразу же после назначения Шеин активно включился в военные дела, обсуждал с царем подробности похода. Петр I был болен, но постоянно сносился со своим главнокомандующим. Об этом достаточно красноречиво свидетельствуют дневниковые записи генерала Гордона за вторую половину января 1696 года: «Был целый день дома, ожидая известия от А. С. Шеина, чтобы с ним вместе ехать к его величеству… Был в городе сначала у А. С. Шеина, затем у его величества… Собирался к государю с главнокомандующим А. С. Шеиным… Виделся сначала с Шеиным, а затем с царем…» и так далее 23 февраля выздоровевший царь уехал в Воронеж где строился флот и собирались запасы для войны. Оттуда Петр I пишет письма своему главнокомандующему, интересуется делами, сообщает о состоянии дорог и мостов.
Сохранилось ответное письмо А. С. Шеина в Воронеж, которое дает представление о том, чем занимался оставшийся в Москве воевода:
«Государь мой милостивой, многолетно здравствуй! За присланное от милости твоей письма и о ведомостях пути и рек, приняв, благодарственно челом бью. И зело сокрушаются, чтоб, не упустя зимнего времени, поспешить на указное место. Доношу милости твоей: толко задержание мое — пехотные полки; отправя с Москвы последние марта 6-го числа, с поспешением буду ускорять до Воронежа, оставя все. А ваша милость в деле своем управляй, как господь вразумит, и Титову[37]
прикажи, чтоб все готово было. Во сем предаюся милоств твоей. Алешка Шеин стократно челом бью».Действительно, уже 15 марта в Воронеж выступил из Москвы сам «воевода большого полку» Алексей Семенович Шеин, проследив за тем, чтобы все его генералы с полками начали движение к месту сбора. 31 марта, «во втором часу ночи», он был уже в Воронеже.
К этому времени строительство флота в основном завершилось. Два тридцатишестипушечных корабля («Апостол Петр» и «Апостол Павел»), двадцать три галеры, четыре брандера, тысяча триста стругов, триста морских лодок, сто плотов — это была внушительная сила, способная решить две стратегические задачи: обеспечить перевозку по реке Дону «ратных людей», «наряда» и необходимых военных запасов и, главное, блокировать крепость Азов с моря.
С 1 апреля началась погрузка на струги пушек, пороха, свинца, ядер, бомб, хлебных запасов. Затем по судам распределили солдатские и стрелецкие полки. За этим следил сам генералиссимус Шеин, решая споры между генералами. Он же инспектировал готовую к отплытию «судовую рать». 10 апреля боярин «пришел к Воронежской пристани к берегу на будары (струги) и устроясь во всем к плавному ходу по воинской обыкности в назначенный военный путь».