Урок первого похода на Азов был усвоен. Решено было выписать военных инженеров из-за границы, что и было поручено дипломатам. Начальствование над всеми вооруженными силами России, которым предстояло вновь действовать под Азовом, было поручено Алексею Семеновичу Шеину. На деле же с этого времени всем руководил Петр.
Приступили и к закладке кораблей. В Преображенском и в Воронеже началось строительство флота. На верфях в Преображенском делались части галер и брандеров. Работали солдаты-преображенцы и семеновцы, выписанные из Архангельска корабельные плотники и юнги. Одновременно заработали верфи в Воронеже, Козлове и других местах.
Десятки тысяч крестьян, солдат и «работных людей» сгонялись на верфи, десятки тысяч возов тянулись на строительство. Сам Петр трудился не покладая рук. Руководил делом Тиммерман.
К концу февраля 1696 г. были готовы части 22 галер и 4 брандеров. Их нужно было доставить для сборки в Воронеж. Это был адский труд. Крестьяне спасались бегством, солдаты бунтовали. Недовольны были «тяготой» бояре и дворяне, не привыкшие к напряженной деятельности, не обученные «морскому делу» и не видевшие в нем проку. Петр строго-настрого приказал им прекратить «дуровать» и угрожал смертной казнью «за оплошку и нерадение».
В середине марта эти суда спустили на воду, а вскоре к ним присоединились большие 30-пушечные корабли «Апостол Петр» и «Апостол Павел», построенные зимой в Воронеже под руководством русского мастера Титова.
Всего флот Петра, предназначенный для действия под Азовом, насчитывал два 36-пушечных корабля «Апостол Петр» и «Апостол Павел», 23 галеры (одна из них голландская), 4 брандера, 1300 стругов, 100 плотов и 30 морских лодок. Для того времени это был сильный флот.
Не забыл Петр и сухопутное воинство. Формировались новые солдатские полки, пополнялись старые полки иноземного строя и стрелецкие, собиралось дворянское ополчение. 13 января Петр издал указ об освобождении от крепостной зависимости тех крестьян, которые запишутся, на военную службу в Азовский поход.
Крестьяне заволновались, потянулись в полки. Заволновались и их господа. Впервые царь Петр встал между крестьянином и помещиком, впервые указал, что крестьянин прежде всего подданный его, государя, и только во вторую очередь — «холоп» своего господина. Но спорить с Петром никто не решался.
Наконец, все было готово. 22 апреля 1696 г. струги вышли в поход. Вслед за ними двинулись корабли и галеры. На галере «Принципиум» плыл и «Петр Алексеев». Вскоре суда достигли низовьев Дона. Казаки донесли Петру, что на взморье стоят два турецких корабля, которые они пытались захватить, но неудачно. Петр решил атаковать неприятельские корабли.
Вечером 19 мая Петр с 9 галерами и 40 казачьими лодками отправился к морю, но суда сели на мель. Тем не менее через некоторое время казаки на своих челнах перебрались через отмели, напали на турок, взяли и сожгли несколько турецких судов. Петр был настойчив. Пользуясь разливом, русские суда пробирались к морю, и 27 мая в водах Азовского моря впервые появился русский флот.
Теперь путь к Азову со стороны моря был закрыт русскими. Началась осада Азова и с суши. Жестокий артиллерийский огонь наносил туркам большой урон. Город горел.
14 июня на горизонте показался турецкий флот из 6 кораблей и 17 галер. Около 4 тыс. воинов и оружие вез он осажденному Азову. Но, увидев русский флот, турки не отважились вступить с ним в бой и ушли обратно в море.
Еще 9 июня приехали «цесарцы» — австрийские инженеры и артиллеристы. Осада пошла еще успешнее. Только дворянское ополчение, нестройное и необученное, воюя «прадедовским обычаем», терпело большой урон от татарской конницы. 17 июля на штурм пошли украинские казаки — «черкасы». Ими были взяты важнейшие турецкие укрепления. Участь Азова была решена. Турки решили сдаться. 18 июля начались переговоры, и вскоре турецкий бей сдался главнокомандующему русских войск Шеину. 21 июля сдался Лютик.
Русские вступили в разрушенный и сожженный их артиллерией Азов. Трофеями русских стали 136 турецких пушек. Для того чтобы закрепить за Россией Азов, в нем был оставлен постоянный гарнизон, насчитывавший 6 тыс. человек, в который входили стрельцы. Подготовлялось заселение присоединенного края русскими переселенцами.
Но, завоевав Азов, Петр еще не открыл себе путь к Черному морю. Выход из Азовского моря в Черное — Керченский пролив охраняли сильные турецкие крепости Еникале, Тамань и особенно Керчь. Для того чтобы продолжать войну с Турцией и открыть России выход к Черному морю, Петр решил строить большой морской флот.