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

1 октября 1695 г. осада была снята и начался отход войск на север, только у каланчей были оставлены русские отряды. Обратно шли сушей по степи, где трудно было найти воду и корм, к тому же наступили морозы. Австрийский посол, сопровождавший русскую армию, писал об отходе русских войск: «По дороге я видел, какие большие потери понесла армия во время своего марша, хотя и не будучи преследуема никаким неприятелем; нельзя было без слез видеть, как по всей степи на протяжении 800 верст лежали трупы людей и лошадей, наполовину объеденные волками» . Удачнее были операции другого войска, действовавшего под началом Б.П.Шереметева вместе с украинскими казаками в низовьях Днепра. Ему удалось захватить четыре небольшие турецкие крепости. Однако неудача под Азовом заставила отказаться от широких замыслов.

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

Главные усилия были направлены на строительство флота, который позволил бы отрезать Азов с моря и лишить его подкреплений. Было решено строить суда двух видов: морские галеры, которые могли ходить под парусами и на веслах и вмещали 120 — 170 человек, и речные струги для перевозки войск по рекам. Лефорт был назначен адмиралом будущего флота. Из Голландии выписали в Архангельск в качестве образца небольшую галеру, которую затем доставили в Москву. Под Москвой были построены 23 галеры и 4 брандера, затем их на санях перевезли на юг, в Воронеж, Судостроительные верфи были устроены в Воронеже, Козлове И й других пунктах на реке Воронеж, откуда суда спускались на Дон. Было приказано к весне построить 1300 речных стругов, 300 морских лодок и 100 плотов.

Для работ по сооружению флота было предписано собрать около 28 тыс. человек. Но часть рабочих совсем не явилась, а многие бежали с мест работы. Условия работы были крайне тяжелы, жалованье было определено по 1 копейке в день, что было совершенно недостаточно. Все же работы велись столь энергично, что флот был выстроен с удивительной быстротой — в течение одной зимы 1695 — 96 г.

Второй Азовский поход начался весной 1696 г. Флотилия из нескольких судов во главе с Петром отправилась вперед из Воронежа и далее Доном. Отплыли 3 мая. К Азову подошли в ночь на 19 мая и остановились у каланчей. На взморье стояли 13 турецких кораблей и галер и 24 мелких судна. Им противостояли 9 русских галер, на которых разместился полк пехоты, и 40 стругов с казаками. Казаки под началом донского атамана Фрола Миняева смело напали на турецкий флот. Им удалось сжечь турецкий корабль и 9 мелких судов и захватить в плен одно судно с продовольствием и сукном.

Уцелевшие турецкие суда спешно ушли в море. После этой победы русский флот из 22 галер собрался в устье Дона, и здесь на обоих берегах реки были сооружены форты, снабженные артиллерией.