Официальное назначение на пост главнокомандующего Алексей Семенович Шеин получил 9 января 1696 г. В дворцовых разрядах сохранился царский указ, по которому Шеину с «товарищи» ведено «быть на своей, великих государей, службе для промыслу под турским городом Азовом». Тогда же был сформирован многочисленный штаб при главнокомандующем: «у большого полкового знамени воевода» стольник князь П.Г. Львов, «генерал-профос» (судья) князь М.Н. Львов, трое «посыльных воевод» (адъютантов), «у ертаула воевода», «у большого наряда и зелейной и свинцовой казны и у всяких полковых припасов воевода». К штабу прикомандировывалось множество московских дворян на разных должностях: 174 «завоеводчика», 108 «есаулов», 8 «обозных», 5 «дозорщиков», 6 «сторожеставцев», 8 «заимщиков» и другие. 18 января к боярину Шеину была «отпущена» из приказа «святыня» – полковое знамя с ликом Христа, с которым царь Иван Грозный ходил в свой славный поход под Казань в 1552 г. (Знамя это хранится в Оружейной палате.) Шеину «отпущены» были также «чудотворный нерукотворенный спасителев образ; святой животворящий крест господень, в нем же власы его спасителевы, которого святого и животворящего креста силой благочестивый царь Константин победил нечестивого Максентия».
Для «письменных дел» в распоряжение генералиссимуса выделялось три дьяка: из Разрядного приказа – Иван Уланов, из Стрелецкого приказа – Михаил Щербаков, из Пушкарского приказа – Иван Алексеев. При Шеине складывалась настоящая походная канцелярия.
Из Посольского приказа прислали переводчика и толмачей с разных языков, из Аптекарского приказа – «дохтура», 17 лекарей, 2 «костоправов» и даже сторожа «при аптеке».
Напрасно некоторые историки намекают, что Алексей Семенович Шеин был вроде «декоративной» фигуры, за спиной которой Петр I фактически руководил военными действиями. Не умаляя достоинств «преобразователя России», хочется все-таки обратить внимание на то, что весь реальный аппарат управления армией находился в руках воеводы Шеина. А «святыни» должны были подчеркнуть в глазах всех его высокое положение…
С этой же целью, как правильно предположил Н.В. Томенко, боярину и воеводе Алексею Семеновичу Шеину было присвоено необычное для тогдашней России высшее воинское звание генералиссимуса.
А подготовка армии к новому походу началась задолго до назначения главнокомандующего. 27 ноября 1696 г. в кремлевской церкви Чудова монастыря появился «сын боярский» из Разрядного приказа и «пошел по церкви кричать, чтобы все стольники, стряпчие, дворяне и жильцы шли в Верх к сказке. Там на Постельном крыльце дьяк Артемий Возницын прочитал им указ: собираться на царскую службу, запасы готовить и лошадей кормить». По всей стране проходил усиленный набор в солдаты и рейтары, причем в царском селе Преображенском записывали даже крепостных крестьян. Всем полкам было приказано собраться к 20 марта в Валуйках и Тамбове.
Армия, предназначенная для похода на Азов, на этот раз состояла примерно из 75 тыс. человек. Подробные сведения о ней имеются в «Описании похода боярина Шеина» (Спб., 1773). Под знамя с «образом Спасовым» становились 30 солдатских полков (38 800 человек), 13 стрелецких полков (9597 человек), 6 «малороссийских» полков (15 тыс. человек), донские пешие и конные казаки (5 тыс. человек), калмыки (3 тыс. человек), яицкие казаки и низовые конные стрельцы (500 человек). В армии также находилось около 4 тыс. московских дворян. Из солдатских и стрелецких полков сформировали 3 дивизии под командованием генералов Головина, Гордона и Ригемана. 3 солдатских полка были выделены Лефорту, назначенному адмиралом. Донскими казаками командовал атаман Фрол Минаев, украинскими – наказной атаман черниговский полковник Яков Лизогуб. Так выглядел командный состав армии А.С. Шеина. И, конечно, важную роль играл и в подготовке, и в самом походе царь Петр I, не занимавший официально «генеральской» должности.
Сразу же после назначения Шеин активно включился в военные дела, обсуждал с царем подробности похода. Петр I был болен, но постоянно сносился со своим главнокомандующим.
23 февраля выздоровевший царь уехал в Воронеж, где строился флот и собирались запасы для войны. Оттуда Петр I пишет письма своему главнокомандующему, интересуется делами, сообщает о состоянии дорог и мостов.
Сохранилось ответное письмо А.С. Шеина в Воронеж, которое дает представление о том, чем занимался оставшийся в Москве воевода:
«Государь мой милостивой, многодетно здравствуй! За присланное от милости твоей письмо и о ведомостях пути и рек, приняв, благодарственно челом бью. И зело сокрушаются, чтоб, не упустя зимнего времени, поспешить на указное место. Доношу милости твоей: толко задержание мое – пехотные полки; отправя с Москвы последние марта 6-го числа, с поспешением буду ускорять до Воронежа, оставя все. А ваша милость в деле своем управляй, как господь вразумит, и Титову[24]
прикажи, чтоб все готово было. Во сем предаюся милости твоей. Алешка Шеин стократно челом бью».