Легче всего было упорядочить командование войсками. Петр назначил вместо трех равноправных командующих двух военных руководителей и каждому из них поручил управление определенным родом войск. Сухопутные войска передавались в руки генералиссимуса Алексея Семеновича Шеина, а для управления пока еще не существующим флотом Петр призвал своего любимца Лефорта. Ни военных дарований, ни ратных подвигов за ними не числилось. Боярин Шеин сделал обычную в то время придворную карьеру, ни разу не побывав на поле брани. Уроженец самой сухопутной страны в Европе, швейцарец Лефорт, весельчак и балагур, не любил утруждать себя какими-либо заботами. К Азову он прибыл позже всех и раньше всех отправился в Москву, к командованию флотом он так и не приступил. Другими военачальниками царь тогда не располагал. Но в данном случае это и не имело значения, так как фактическим руководителем похода являлся он сам, а Шеин и Лефорт были всего лишь подставными лицами.

Сложнее было призвать под знамена второго похода конное ополчение дворян, которое всегда распускали по домам на зиму. В этом случае действовала хотя и тяжеловесная, но испытанная десятилетиями система мобилизации ополченцев: в уезды были отправлены указы, а в столице 27 ноября дьяк Артемий Возницын трубным голосом объявил дворянам, приглашенным в Кремль: «Стольники, стряпчие, дворяне московские и жильцы! Великие государи указали вам всем быть на своей, великих государей, службе. И вы бы запасы готовили и лошадей кормили». Местом сбора назначалось Преображенское, куда надлежало явиться 1 декабря.

В комплектование войск царь ввел новшество — в январе было объявлено, чтобы в Преображенское являлись все, кто имеет желание участвовать во втором походе. Туда потянулись жившие в Москве холопы, которые тут же получали свободу.

Самым трудным делом, прежде всего потому, что оно было совершенно новым, считалось строительство кораблей, причем не мелких судов для перевозки солдат, продовольствия и снаряжения — их строить умели, — а боевых кораблей. Именно здесь, на ответственном участке подготовки похода, и находился царь.

Похоронив в конце января нового, 1696 года своего брата Ивана, Петр в феврале отбыл на верфь в Воронеж, где начал осуществлять поистине великий замысел — в дотоле сухопутной стране создать морской флот. Этот дерзкий вызов стал действительностью много лет спустя.

А пока полным ходом шло строительство стругов и галер. Несколько тысяч плотников, согнанных из ближайшей округи, сооружали 1300 стругов. С топором в руках трудился и сам царь.

Дело в Воронеже спорилось, и Петр счел долгом донести об этом «князю-кесарю»: «галеры и иные суда по указу вашему строятся; да нынче же зачали делать на прошлых неделях два галиаса».

В начале мая сосредоточенная в Воронеже армия и военный флот в составе 27 судов двинулись на юг. В конце месяца войска заняли под стенами Азова прошлогодние траншеи и начали обстрел города. До штурма крепости дело не дошло — ее судьбу решил флот. Сначала казаки на мелких судах напали на разгружавшиеся турецкие корабли у стен Азова и уничтожили их, а затем в Азовское море вышла русская эскадра. На рейде стояли турецкие корабли с 4 тысячами человек пехоты и запасами продовольствия и снаряжения. Их попытка прорваться к Азову не увенчалась успехом. Крепость оказалась в кольце блокады, и гарнизон принял условия капитуляции. Русское командование поставило непременным условием выдачу ему «немчина Якушки», того самого перебежчика Янсена, по совету которого во время прошлогодней осады турки предприняли удачную вылазку.

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