Самое комплектование войска происходило теперь не так, как прежде. 13 декабря кликнули клич в Москве, чтобы поступали на службу ратную охочие люди всякого чина. «Охотников нашлось немало, – говорит историк, – особенно в господских дворнях, наполненных сотнями холопов праздных и голодных. Крепостные люди толпами стекались в Преображенское и записывались – частию в солдаты, частию в стрельцы. Жен и детей их отбирали от господ и селили в Преображенском» (том II, стр. 261). Кроме того, Петр потребовал присылки войск от малороссийского гетмана и из Белгородской армии. Над всем войском назначен был один главнокомандующий, чего не было в первом походе и что много мешало единству действия. В декабре же, сделавши распоряжение о заготовлении материалов для постройки судов в Воронеже, Петр занялся формированием морского региментпа, который и составился из 4000 человек, частию вновь набранных, частию переведенных из Семеновского и Преображенского полков. Начиная с марта месяца Петр занялся уже почти исключительно постройкою судов.
Г-н Устрялов свидетельствует, что и в это время Петр «еще не думал о постройке фрегатов и линейных кораблей, вопреки рассказам позднейших историков. Желания его ограничивались гребною флотилиею, галеасами, галерами, каторгами, брандерами» (том II, стр. 259). Значит, и здесь у Петра была только ближайшая цель: соорудить флотилию, чтобы запереть Азов с моря. Определенная мысль о флоте как «краеугольном камне могущества России и лучшем средстве открыть России путь в Европу» – явилась еще позднее. Флотилия Петра состояла теперь из 30 военных судов, сооруженных под его надзором и при его непосредственном участии в течение марта месяца 1696 года. К половине апреля подошли в Воронеж войска из Москвы, а через месяц Петр был уже под Азовом. Здесь, с первого же шагу, Петр мог заметить, что турки робеют на море и что на галеры его смотрят не без страха. Не мудрено, что это, как предполагает г. Устрялов, убедило Петра в пользе и надобности построить флот, который мог бы плавать по волнам не только азовским, но и черноморским. Впоследствии мы видим, что при переговорах с турками Петр очень добивался дозволения русским кораблям свободного плавания по Черному морю.
Под Азовом дела на этот раз шли гораздо лучше, хотя до прибытия цесарских инженеров мы умели только повреждать строения в городе нашими бомбами и ничего не могли сделать укреплениям. Бывали и в самых битвах не совсем удачные попытки, как, например, 24 июня, когда русские, отразив татар, бросились их преследовать, по словам самого Петра, «прадедовским обычаем, не приняв себе оборонителя воинского строю», и оттого потерпели значительный урон. Но все же теперь было уж далеко не то, что в первой осаде. Только искусство вести осадные работы нам не давалось, несмотря даже на присутствие приезжих бранденбургцев, которые оказались артиллеристами и были искусны только в метании бомб. Не зная, что делать, спросили самих солдат и стрельцов, как им кажется лучше овладеть Азовом. Они сказали, что нужно сделать высокий земляной вал, привалить его к валу неприятельскому и, засыпав ров, сбить турок с крепостных стен. «Как ни странно было это предложение, напоминавшее осаду Херсона великим князем Владимиром в X столетии, – замечает г. Устрялов (том II, стр. 285), – однако же царский совет принял эту мысль, а Гордон даже с жаром ухватился за нее… Принялись строить вал, и более двух недель постоянно по ночам работали над ним по 15 000 человек… Само собою разумеется, что работы эти не обходились без значительных потерь для нас, а пользы пока приносили мало. Наконец приехали 11 июля цесарские инженеры, подивились громадности работ наших, но не ожидали от них особенного успеха, а более надеялись на подкопы и батареи. Они дали советы, как вести мины, как ставить батареи, и вскоре меткие выстрелы их разрушили палисады, которые тщетно старался разбить Гордон. На ночь 12 июля русские солдаты могли уже занять оставленный турками угловой бастион; через неделю турки не могли более выдерживать нашей пальбы и заговорили о сдаче. На другой день решена была капитуляция. Турецкое войско выпущено с оружием. Петр занял Азов, предположил построить новые укрепления для него, потом отправился отыскивать в Азовском море место, удобное для гавани будущего флота русского. Место это нашлось близ Таганрога. Вскоре потом войска пошли назад и через два месяца, 30 сентября, вступили в Москву с торжественнейшим триумфом. Через месяц потом (в начале ноября) решено было Петром устройство