Осада крепости три месяца длилась безрезультатно. На одной из батарей бомбардир Петр Михайлов лично начинял гранаты и палил по городу в течение двух недель. Так началась воинская служба царя, о чем он оставил запись в дневнике: «Зачал служить с первого азовского походу бомбардиром». Русское командование решило штурмовать крепость. Организовали набор добровольцев. Каждому было обещано денежное вознаграждение в размере 10 рублей. Обе каланчи взяли. Захватить штурмом Азовскую крепость, гарнизон которой насчитывал 7 тысяч, ни с первой, предпринятой 5 августа, ни со второй, предпринятой 25 сентября, попытки не удалось. В крепость турки доставляли морем боеприпасы и провиант, а русские несли большие потери и ничего не могли предпринять в ответ. Отсутствие «искусства атаковать крепости», специалистов подрывных операций имел печальные последствия. Главный инженер Франц Тиммерман, с которым юный царь познакомился в Немецкой слободе, не смог наладить подрывную работу. В помощники ему царь назначил А.А. Вейде, Я.В. Брюса. Уже при первой попытке заложить порох в подкопе камеры обнаружился непрофессионализм инженеров. Гордон указывал, что взрыв, произведенный раньше времени, вызовет ненужные жертвы. Царю хотелось быстрее подорвать стену и через пролом запустить в крепость солдат. Взрыв прогремел, стена, как и предполагал Гордон, так и продолжала стоять, а солдат погибло много. Артиллерия не сумела пробить бреши в крепостной стене. Штурмовавшие команды действовали без предварительного согласования, что позволило туркам своевременно перегруппироваться и дать отпор. Армия Шереметева заняла две небольшие турецкие крепости. В сентябре у Гордона один из полков уничтожили татары, а командир полка попал в плен. Петр I решил снять осаду Азова, и в конце сентября на генеральском совете посчитали кампанию закрытой. В новопостроенной напротив Азова крепости Сергеевской и для охраны каланчей русское командование оставило гарнизон в 3 тысячи человек под командованием воеводы Акима Ржевского. На зиму в Азове оставили и стрельцов. Путь отступления был сложным. Только по Дону требовалось пройти 1 тысячу верст. Степь замело снегом, выл пронизывающий холодный ветер. По воспоминаниям очевидца, нельзя было «…без слез и содрогания видеть множество трупов, разбросанных на пространстве 800 верст и пожираемых волками». Единственного турка, взятого в плен, удалось спасти. Его водили по столичным улицам и, как обезьянку, показывали людям.

Вернувшись в Москву, Петр I созвал совет, состоявший из Б.П. Шереметева, А.Д. Меншикова, Ф.А. Головина и Ф.Ю. Ромодановского. Царь подготовил записку «Статьи удобные, которые принадлежат к взятой крепости или фортеции турок Азова». Указав на недостаток вооружения, слабую выучку стрельцов и дворянской конницы, плохо подготовленную осадную технику во время проведения Первого Азовского похода, Петр I счел необходимым начать строительство российского флота. Еще в 1692 году Петр I пришел к необходимости строить военно-морской флот в Архангельске, единственном на тот момент порту России. На его верфях был заложен первый 44-пушечный корабль.

Царь предложил разделить повинность между податным населением. Патриаршество и духовенство обязывались собрать средства на постройку одного корабля с 8 тысяч крестьянских дворов, а бояре и служилые люди — с 10 тысяч крестьянских дворов. Строили корабли в Воронеже, возведенном как крепость в 1585 году. Место царь выбрал не случайно. Река Воронеж являлась судоходной и впадала в Дон, что открывало новые перспективы для российской политики. Кроме того, немаловажное значение имело и то, что население, проживавшее на берегах Воронежа, знало толк в строительстве речных судов. Но строительство шло плохо. Крестьяне бежали. По велению царя привлекли солдат-ремесленников. Люди работали на износ. За короткий срок построили два 36-пушечных корабля, двадцать три галеры, четыре брандера, одну тысячу триста стругов. 2 апреля 1696 года на воду спустили первые русские галеры «Святой Марк», «Святой Матвей», «Принципиум». Под командованием воеводы А.С. Шейна сформировали Азовскую армию. Войско увеличилось вдвое и составило 75 тысяч человек. Личный состав Азовской флотилии набирали преимущественно из солдат Семеновского и Преображенского полков. Стали готовиться к новому походу. В поисках хороших инженеров царь обратился за помощью к польскому королю и австрийскому императору.

В апреле 1696 года под общим руководством Петра I был предпринят Второй Азовский поход. Сбор войска назначили в Воронеже. Сюда же подошли 15 тысяч малороссийских, запорожских, 5 тысяч донских и яицких казаков. С Преображенского двора из Москвы в разобранном виде доставили построенные корабли. Всего собрали для похода 522 струга, 42 мореходных лодки, 134 плота. Донской атаман Л. Поздеев донес царю, что разведчики показали: в Азовском море появился турецкий флот, состоящий из 15 хорошо вооруженных кораблей, 13 больших галер, 13 полугалер со вспомогательными войсками и снарядами. 27 мая авангард русского флота вышел в Азовское море. А 12 июня Азов блокировали с моря. Турки предприняли попытку прорваться к Азову, но подойдя к устью Дона 14 июня и обнаружив русские галеры, турецкий десант ушел обратно в море. Приезд иностранных инженеров — специалистов по осаде крепостей задерживался. Как позже выяснилось, русский посол дьяк Е.И. Украинцев решил не допустить утечки информации, поэтому ничего не сообщил русскому послу в Вене П.Б. Возницину, отправлявшему иностранцев в Россию. Возницин без суеты подготовил отъезд инженеров. 16 июня начали бомбардировать крепость. Массированная артиллерия сыграла неоценимую помощь в захвате. Шейн предложил возвести земляную гору высотою с вал, окружавший крепость. 23 июня ночью на суше по проекту П.И. Гордона 15 тысяч солдат и казаков начали строить вал, превышающий но замыслу крепостные стены. 25 июня прибыли иностранцы. Руководство осадой перешло к специалистам — инженерам и офицерам-артиллеристам из Австрии, Голландии, Бранденбурга. Тут случилось непредвиденное. Первыми не выдержали запорожцы, которым надоели земляные работы, за ними выступили донские казаки. Не дожидаясь общего штурма, 17 июля два полка казаков во главе с атаманом Я.К. Лизогубом начали штурмовать крепость, захватив часть наружного крепостного вала. 18 июля на русский лагерь напали татары. Солдаты отбили атаку, но не смогли прийти на помощь казакам. На 19 июля царь назначил штурм. Азовский гарнизон насчитывал 3 тысячи 700 «штыков» и 5 тысяч 900 мирных жителей. Турки, видя, что готовится штурм основными силами, выслали из Азова парламентеров. 18 июля 1696 года пал Азов. 20 июля сдался гарнизон небольшой крепости Лютик, стоявшей на реке Мертвый Донец напротив Азова. 20 октября 1696 года Боярская дума закрепила законодательно решение о строительстве флота. Была утверждена обширная программа судостроения. Решили построить 52 судна, введя новые повинности для всех слоев населения. Как правило, историки пишут об указе, принятом боярами. Е.В. Тарле нашел фрагменты обсуждения программы, которые ныне хранятся в документах Росийского государственного архива древних актов, что и позволило в дальнейшем историкам писать о законодательном характере принятого постановления.

В честь победы царь приказал выбить медаль с изображением Петра и надписью: «Молниями и водами победитель». За успешные действия во Втором Азовском походе воевода Алексей Шейн первым в России получил чин генералиссимуса. Ф. Головина царь наградил золотой медалью, кубком и поместьем на Орловщине и назначил его управляющим Малороссией. Усиление российских позиций под Азовом привело к ограничению прав донских казаков. Донское казачество лишилось свободного выхода в Азовское море по Дону.