Для «письменных дел» в распоряжение генералиссимуса выделялось три дьяка: из Разрядного приказа – Иван Уланов, из Стрелецкого приказа – Михаил Щербаков, из Пушкарского приказа – Иван Алексеев. При Шеине складывалась настоящая походная канцелярия.

Из Посольского приказа прислали переводчика и толмачей с разных языков, из Аптекарского приказа – «дохтура», 17 лекарей, 2 «костоправов» и даже сторожа «при аптеке».

Напрасно некоторые историки намекают, что Алексей Семенович Шеин был вроде «декоративной» фигуры, за спиной которой Петр I фактически руководил военными действиями. Не умаляя достоинств «преобразователя России», хочется все-таки обратить внимание на то, что весь реальный аппарат управления армией находился в руках воеводы Шеина. А «святыни» должны были подчеркнуть в глазах всех его высокое положение…

С этой же целью, как правильно предположил Н.В. Томенко, боярину и воеводе Алексею Семеновичу Шеину было присвоено необычное для тогдашней России высшее воинское звание генералиссимуса.

А подготовка армии к новому походу началась задолго до назначения главнокомандующего. 27 ноября 1696 г. в кремлевской церкви Чудова монастыря появился «сын боярский» из Разрядного приказа и «пошел по церкви кричать, чтобы все стольники, стряпчие, дворяне и жильцы шли в Верх к сказке. Там на Постельном крыльце дьяк Артемий Возницын прочитал им указ: собираться на царскую службу, запасы готовить и лошадей кормить». По всей стране проходил усиленный набор в солдаты и рейтары, причем в царском селе Преображенском записывали даже крепостных крестьян. Всем полкам было приказано собраться к 20 марта в Валуйках и Тамбове.

Армия, предназначенная для похода на Азов, на этот раз состояла примерно из 75 тыс. человек. Подробные сведения о ней имеются в «Описании похода боярина Шеина» (Спб., 1773). Под знамя с «образом Спасовым» становились 30 солдатских полков (38 800 человек), 13 стрелецких полков (9597 человек), 6 «малороссийских» полков (15 тыс. человек), донские пешие и конные казаки (5 тыс. человек), калмыки (3 тыс. человек), яицкие казаки и низовые конные стрельцы (500 человек). В армии также находилось около 4 тыс. московских дворян. Из солдатских и стрелецких полков сформировали 3 дивизии под командованием генералов Головина, Гордона и Ригемана. 3 солдатских полка были выделены Лефорту, назначенному адмиралом. Донскими казаками командовал атаман Фрол Минаев, украинскими – наказной атаман черниговский полковник Яков Лизогуб. Так выглядел командный состав армии А.С. Шеина. И, конечно, важную роль играл и в подготовке, и в самом походе царь Петр I, не занимавший официально «генеральской» должности.