Неудача, несмотря на попытки ее скрыть, огласилась. Потери Петра были не меньше потерь Голицына в 1687 и 1689 гг. Недовольство в народе против иноземцев, которым приписывали неудачу, было очень велико. Петр не падал духом, не прогнал иноземцев и не оставил предприятия. Впервые показал он здесь всю силу своей энергии и в одну зиму, с помощью иноземцев, построил на Дону, в устье реки Воронежа, целый флот морских и речных судов. Части галер и стругов строили плотники и солдаты в Москве и в лесных местах, близких к Дону. Эти части свозились в Воронеж и из них собирались уже целые суда. Много препятствий и неудач преодолел царь, ставший в это время единодержавным государем (брат Петра, царь Иван, умер 29 января 1696 г.). На Пасху 1696 г. в Воронеже уже были готовы 30 морских судов и более 1000 речных барок для перевозки войск. В мае из Воронежа Доном двинулось русское войско к Азову и вторично осадило его. На этот раз осада была полной, ибо флот Петра не допускал к Азову турецких кораблей. На суше под единоличным начальством боярина Шеина дела шли счастливо. Петр сам присутствовал в войске (в чине капитана) и, наконец, дождался счастливой минуты: 18 июля Азов сдался на капитуляцию.

Как тяжела была раньше неудача, так велика была радость в Москве при получении известия о победе. Радовался и сам Петр: в успехе он видел оправдание своей предшествовавшей деятельности, своих «потех». Победа была отпразднована торжественным вступлением войск в Москву, празднествами и большими наградами. Торжественно были извещены и союзники о русской победе. В Польше и на Западе не ждали такого успеха Петра и были им поражены. Слух о взятии Азова прошел по всей Европе. Польские дипломаты плохо скрывали свой страх, внушаемый им политическими успехами соседки – Москвы. Сами москвичи со времени царя Алексея не видали таких побед и находились под обаянием взятия Азова.

И после победы, как после неудачи, Петр не опустил рук. Зима 1696/97 г. прошла в заботах об укреплении Азова и о построении флота для Азовского моря. В Азов решено переселить 3000 семей из волжских городов и 3000 стрелецкого войска. Построение флота решено было совершить силами и средствами всего государства: таким образом создалась своеобразная земская повинность: с каждых 10 000 крестьянских дворов, принадлежавших светским владельцам, правительство желало получить снаряженный корабль; с каждых 8000 крестьянских дворов духовных владельцев – то же самое. Городское сословие всего государства должно было снарядить 12 кораблей. Для этой цели землевладельцы должны были съехаться в Москву, образовать компании («кумпанства»), разверстать издержки и повинности и готовить корабли в 1698 г. Правительство же снабжало кумпанства инструкциями и необходимыми чертежами.