Эти отбитые штурмы, надвигавшаяся осень с ветрами и непогодами заставили Петра отложить взятие Азова. 28 сентября осада была снята, царское войско отошло сначала к Черкасску, а потом ушло на зимовку к Валуйкам. Донские сотни разошлись по станицам. Во взятых казаками каланчах азовских было оставлено 3000 человек солдат.
По всему Дону пошли рассказы о молодом царе. Сильное впечатление произвел он на казаков. Царь был громадного роста, без 2-х вершков сажень, широкий в плечах, с круглым открытым лицом и большими ясными, смелыми глазами. Он носил немецкую одежду, говорил властно и в то же время приветливо. «Орел, настоящий орел!» - в восторге говорили казаки и готовы были отдать за своего государя все. И сама собою сложилась на Дону песня про первый приезд на Дон государя:
Первая морская победа Петра 1696 г.
Но молодой царь после этой неудачи не пришел в отчаяние. Он решительно начал готовиться к новому походу. На первый поход он смотрел лишь как на школу. Он понял теперь, что морскую крепость без кораблей взять нельзя. По всем местам пошли его приказы. 8 января 1696 года царь послал донцам наказ занять каланчи и поддерживать солдат до подхода всего войска. Но это уже исполнено было донцами еще до получения царской грамоты. 600 казаков стояло в каланчах.
В то же время вызваны были из Италии искусные «подкопные» мастера. В Воронеже строили верфь, то есть корабельный завод, заготовляли лес и делали корабли. Петр сам писал морской устав. Снаряжалось сильное войско. Главным начальником его был назначен боярин Шеин.
В конце апреля донские казаки с удивлением увидали целый караван больших морских кораблей на Дону. Впереди шло восемь гребных лодок, или галер, управляемых преображенцами и семеновцами. На одной из них, называемой «Принципиум», находился под видом капитана, командира роты Преображенского полка Петра Алексеева, царь.
По прибытии в Черкасск Петра войсковой атаман Фрол Минаев доложил государю, что посланный на разведку походный атаман Поздеев с 250 казаками 3 мая увидал в море два турецких корабля. Он обступил их своими легкими лодками, обстрелял ружейным огнем и хотел с одними только саблями взять суда. Но борта кораблей были высоки, казаки пытались прорубить их днища, но турки бросали в казаков камни и заставили их отступить.
Разгорелось сердце у молодого царя. Присутствие турецкого флота у стен Азова возбуждало Петра. Хотелось ему померяться со смелым врагом силами. 12 мая царь со своими судами подошел к Каланчинским башням и хотел выйти в море. Но дул северо-восточный ветер и согнал воду с Дона, а суда царские сидели глубоко и не могли пройти через мелкое устье. Тогда царь оставил галеры в Кутюрминском рукаве и со ста донскими легкими лодками, на которых было 6000 казаков с атаманом Фролом Минаевым, обошел все гирла и вышел в море.
Широкий водный простор представился глазам Петра. Первый раз вышел он в южное море. Зеленовато-синие волны играли под налетами вечернего ветерка и звучно плескались о казачьи челны. Русский царь был один со своими казаками, и легко и привольно ему было на сердце с этими природными моряками. В каждом взмахе их весел, в том, как уверенно показывал и называл мысы и острова стоявший рядом с ним атаман, Петр видел, что на синем море казаки как у себя дома.
- Вот здесь, - скажет кто-либо из казаков, - убит мой дед.
- У этого мыска потонул мой отец!
Скажут и смолкнут. Все лица серьезны. Враг кругом. Заходящее солнце бросает кровавые отблески на стены и башни Азова. И море играет белопенным прибоем возле них.
На море видны паруса. Это турецкий флот идет на выручку Азову; зоркий казачий глаз насчитал уже девять больших кораблей и несколько гребных галер.