Из солдатских и стрелецких полков должно было сформировать три дивизии — Гордона (14 117 человек), Головина (13 738 человек) и Ригемана (10 299 человек). Отдельный отряд из 3-х солдатских полков численностью в 4000 назывался пешим полком адмирала Лефорта.

Сборным местом назначили Валуйки и Тамбов, где войскам надлежало собраться к 20 марта, чтоб не позже 1 мая 1696 года быть у Черкасска.

14 декабря Петр собрал Гордона, Лефорта и Головина, и они стали выбирать единого главнокомандующего. Ясно, что если так выбирают, то возьмут кого-нибудь со стороны, чтоб никому из присутствующих обидно не было. Выбрали престарелого князя Михаила Алегуковича Черкасского, «почтенного заслугами и характером», который проявил верность ветви Нарышкиных еще при владычестве Софьи. Но князь Черкасский болел и от такой чести вскоре отказался. Тогда 9 января генералиссимусом Петр наименовал боярина Алексея Семеновича Шейна, правнука доблестного защитника Смоленска. И правильно, по заслугам. Во время Крымских походов Шейн вторым в войске после Василия Голицына был, Новгородским разрядом командовал.

Новым, чего не предвидел никто, было решение Петра строить в Воронеже флот. 30 ноября в письме к Двинскому воеводе Апраксину сообщал он: «По возвращении от невзятия Азова, с консилии господ генералов указано мне к будущей весне делать галеи».

Настоящие морские фрегаты и линейные корабли к весне построить было просто невозможно. Строить решили гребной флот — галеасы, галеры, каторги и брандеры.

По обеим сторонам реки Воронежа росли дубовые, липовые, буковые, сосновые леса. Здесь всегда строили плоскодонные струги для перевозки Доном жалования Войску Донскому, для отправки посольств. Бывало, что по 20 тысяч наряжали людей из окрестных городов на строительство стругов, и строили они зимою в лесах караваны по 500 и более судов, а весной на станках с колесами подвозили и спускали их на воду.

На реке Воронеже, в 15 верстах от впадения ее в Дон, повелел царь основать верфь. Стольник Григорий Титов должен был с людьми к февралю распилить 7000 деревьев на брусья, бруски, пластины и доски по данным ему чертежам, собрать у местных жителей смолу и конопать, выписать с железных заводов скобы, крючья и гвозди и все это сложить под Воронежем на Луговой стороне к приезду царя. Из Архангелска выписаны были свои и иноземные мастера кораблестроения. А в качестве образца отправили в Воронеж из Москвы заказанную в Голландии и оттуда доставленную галеру.

Планировал царь построить 300 таких галер, чтоб размещались в них 120–170 человек солдат, и 1300 стругов для размещения артиллерии, запасов и генералов с их свитами. Заранее стал готовиться уже озвученный морской регимент в 28 рот в числе 4000 человек. Направляли туда из Преображенского и Семеновского полков и из вновь набранных солдат.

В начале 1696 года Петр уехал в Москву, где 29 января скончался брат и соправитель его Иоанн. Похоронив брата, 23 февраля выехал он в Воронеж, там уже собрались 26 тысяч работных людей, и немедленно включился вместе с ними в работу.

На Дону не ждали в ближайшее время никаких особых событий.

Крупнокалиберная артиллерия, боеприпасы, всяческое снаряжение русской армии зимовали в Черкасске, в специально построенных Гордоном амбарах. Многие, помня, как уходила русская армия, втихомолку уже считали это имущество своим.

С уходом армии казаки вернулись в обычную колею. А колея эта — наскучившее и неизбежное противостояние с Азовом.

В конце декабря в Черкасске узнали, что Муртаза-паша намеривается вернуть каланчи, и на 1 января 1696 года крупная партия казаков, конных и пеших, силою 2000, подтянулась к Ново-Сергиевскому городку. После военного совета с воеводою Ржевским казаки «по своей казачьей обыкности пристойные места залегли», то есть остались снаружи, скрытно, и выслали к городу 50 всадников «для языков». Казачья разведка была встречена выстрелами и вылазкой. Казаки быстро отступили в сторону каланчей и стали ждать. Как и ожидалось, появились азовцы и напали на городок. 7 человек из гарнизона они переранили и хотели увести в плен, но казаки ударили по ним из засады, «в полон тех ратных людей взять не дали, и гнали за теми неприятели от Сергиева до самого Азова и взяли из них знатного азовского татарина». Знатность его проявлялась в том, что он до этого 14 человек переранил и 7 стрельцов в плен взял.

Пленного отправили в Москву, и в Москве «по допросным того взятого татарина речам явилось, что от Хана Крымского пришла в Азов подлинная ведомость: отпущен де в Азов из Крыму Шабан-Гирей салтан, а с ним 900 емаков, пеших людей; а в Тамани, и в Керчи и в иных ближних городах Муртоза паша с братьями с пехотою яныченскою в готовности, и ждут их азовцы к себе вскоре; а будет та пехота с Шабан-Гиреем салтаном и с Муртозою с казною и со всякими хлебными запасы на 5000 арбах, да на тех же арбах прислано будет 20 мозжеров (мортир), а с теми мозжеры 50 человек мастеров, да с нагайскою ордою и с черкасы и со всею конницею большим собранием будет другой салтан — Каплан-Гирей; а приказал де хан, чтоб тем их поганеким войскам иттить мимо Азова и приступать к Сергиеву и мозжерами город зажечь; а из Царягорода от салтана прислано будет со льдом вместе войско для строения Азова и к тому строению в Азов прислано мастеров 10 человек». То есть, турки и татары собирали силы, чтобы вернуть себе каланчи и отстроить Азов после недавней осады.

Казаки трезво рассчитали, что взятие турками каланчей закончится их походом на Черкасский городок, чтобы, пользуясь случаем, решить заодно и казачий вопрос. Поэтому они решили удерживать неприятеля на дальних подступах «и послали в Сергиев ратным людям на помочь 400 человек казаков и велели им стоять и оборону против неприятелских людей чинить, не щадя голов своих». А заодно усилили караулы в самом Черкасском городке и «для того поставили… у пушечной и у пороховой казны на сторожу 200 человек казаков».

Приход азовцев под Новосергиевский был воспринят Москвой как разведка боем. И на Дон немедленно послали самые подробные инструкции: «И вы б (…) новопостроенный город Сергиев и Каланчи от неприятелского навождения берегли со всяким усердным радением и до взятия и ни до кокого разорения не допустили. И послать бы вам от себя из войска в тот город и в каланчи в помочь того города, к прежним ратным людем в прибавку казаков добрых, сколько человек пристойно, без всякого мотчания, чтобы тех казаков в осаду и на отпор неприятелем было доволно, и чинить отпор с великим радением, обще с ратными людми, которые в Сергиеве и на каланчах оставлены, и были б те казаки в том городе и на каланчах до приходу ратных московских и городовых полков не отлучно, и о приходе неприятелских людей проведывать всячески с великим радением, и с Сергиевским воеводою о бережении того города и каланчей чинить бы вам пересылки безпрестанные и от неприятелей опасные, а буде учинится к тому городу и к каланчам приход многих неприятелских людей и учнут под тем городом и каланчами стоять и приступать, и вам бы (…) всем войском к тому городу и к каланчам итти и от неприятелей тот город и каланчи (…) боронить (…) и показать в том службу и радение свое и до разорения, конечно, не допустить, чтобы тем неприятеля приступу и порадованья, а впредь будущему нашему воинскому промыслу помешки не учинить, а будет от неприятелей, сохрани Боже, Сергееву городу и Каланчам учинится взять или иное какое разрушенье; и то все причтено будет в ваше нерадение; и писали б вы от себя с Дону в верхние городки к атаманом и казаком с нарочными гонцы наскоро, чтобы они из верхних городков шли к вам в Черкаской на помочь тотчас, безо всякого мотчания и чинили б над неприятели воинские промыслы и осторожность всякую с вами обще, заодно, да и в Черкаском нашей, великого государя, казны со всякою осторожностию беречь же; а служба ваша и радение у нас (…) в забвении не будет, в том бы вам на нашу (…) милость быть надежным».