По возвращении в Москву обсуждался план нового похода. Причинами неудачи были признаны: отсутствие русского флота, недостаток инженеров, опытных в осадных работах, и отсутствие единства командования. Решено было выписать инженеров из-за границы. Новым главнокомандующим сухопутных сил был назначен боярин А. С. Шейн, а Петр взял на себя общее руководство походом.
Главные усилия были направлены на строительство флота, который позволил бы отрезать Азов с моря и лишить его подкреплений. Было решено строить суда двух видов: морские галеры, которые могли ходить под парусами и на веслах и вмещали 120 — 170 человек, и речные струги для перевозки войск по рекам. Лефорт был назначен адмиралом будущего флота. Из Голландии выписали в Архангельск в качестве образца небольшую галеру, которую затем доставили в Москву. Под Москвой были построены 23 галеры и 4 брандера, затем их на санях перевезли на юг, в Воронеж, Судостроительные верфи были устроены в Воронеже, Козлове И й других пунктах на реке Воронеж, откуда суда спускались на Дон. Было приказано к весне построить 1300 речных стругов, 300 морских лодок и 100 плотов.
Для работ по сооружению флота было предписано собрать около 28 тыс. человек. Но часть рабочих совсем не явилась, а многие бежали с мест работы. Условия работы были крайне тяжелы, жалованье было определено по 1 копейке в день, что было совершенно недостаточно. Все же работы велись столь энергично, что флот был выстроен с удивительной быстротой — в течение одной зимы 1695 — 96 г.
Второй Азовский поход начался весной 1696 г. Флотилия из нескольких судов во главе с Петром отправилась вперед из Воронежа и далее Доном. Отплыли 3 мая. К Азову подошли в ночь на 19 мая и остановились у каланчей. На взморье стояли 13 турецких кораблей и галер и 24 мелких судна. Им противостояли 9 русских галер, на которых разместился полк пехоты, и 40 стругов с казаками. Казаки под началом донского атамана Фрола Миняева смело напали на турецкий флот. Им удалось сжечь турецкий корабль и 9 мелких судов и захватить в плен одно судно с продовольствием и сукном.
Уцелевшие турецкие суда спешно ушли в море. После этой победы русский флот из 22 галер собрался в устье Дона, и здесь на обоих берегах реки были сооружены форты, снабженные артиллерией. Вскоре к Азову приблизился турецкий флот из 23 кораблей, пытавшийся высадить десант, но при виде русских галер турки отступили. Таким образом, Азов был осажден с моря и суши На предложение сдаться турки ответили стрельбой.
Началась осада крепости. Солдаты предложили насыпать высокий вал под крепостью. Земляные работы шли успешно, вал сравнялся высотой со стенами крепости, ров перед ней был засыпан, и казаки захватили одно из турецких укреплений.
Среди турецкого гарнизона Азова произошел раскол: одна часть стояла за продолжение борьбы, другая настаивала на сдаче города русским, так как в крепости был недостаток припасов и снарядов и находилось много раненых и больных. Однако на новое предложение о сдаче турки опять ответили отказом. Тогда на военном совете 18 июля было решено через три дня приступить к общему штурму крепости. Но в этот же день турки стали махать из Азова шапками и преклонять знамена в знак желания начать переговоры. Они согласились сдать крепость на предложенных им условиях, с правом уйти из нее «безопасно и с имуществом».
19 июля 1696 г. турецкие войска покинули Азов. Они шли между двумя рядами русских войск. Турецкий комендант и другие начальники преклонили свои знамена к ногам глав-иокомандующего боярина Шейна. Азов в тот же день был занят русскими войсками. Победа над турками была отпразднована в Москве. Были сооружены триумфальные ворота для торжественной встречи возвращающейся армии. Триумфальную арку украсили колоннами и статуями. Здесь были изображены азовский паша и два скованных турка; надпись гласила: «Ах! Азов мы потеряли и тем бедство себе достали». По сторонам ворот были помещены картины, написанные на полотне. На одной из них был изображен древнеримский бог морейчНептун с надписью: «Се и аз поздравляю взятием Азова и вам покоряюсь». Войска проходили через всю Москву. У триумфальной арки трубач произносил приветствие, составленное в стихах и прославлявшее подвиги армии и ее руководителей. За войсками волокли по земле турецкие знамена и вели пленных. Шествие продолжалось с утра до вечера, никогда Москва не видела такой великолепной церемонии.
Взятие Азова было крупным событием, оно явилось началом превращения России в морскую державу. Но присоединения одного Азова было недостаточно, надо было добиться доступа к Черному морю. Для успешного продолжения войны нужны были новые средства и прежде всего-необходим был большой морской флот. По предложению Петра Боярская дума приняла решение о сооружении флота из 52 крупных кораблей. Постановление это от 20 октября 1696 г начиналось словами: «Морским судам быть...» Этот день можно считать «днем рождения» русского военно-морского флота.