Яков Мороз несколько дней на 40 чайках крейсировал в море, пока не заметил турецкий караван. В ходе боя было захвачено три судна, на одном из которых были обнаружены письма султана к крымскому хану. При возвращении назад отряд Мороза у Очакова также был перехвачен турецкими галерами. Казаки пристали к берегу затопили чайки и прорвались в Сечь пешком, приведя с собой 27 пленных турок.

30 сентября 1696 г. состоялся торжественный въезд победителей под Азовом. Войска, растянувшиеся на много километров, прошли через Москву Впереди ехал адмирал Лефорт и генералиссимус Шеин, а за ними пешком с протазаном — капитан Петр Алексеев.

Пышность встречи не соответствовала масштабам победы. Кстати, и Петр не питал излишних иллюзий на этот счет. По поводу взятия Азова он заявил приближенным: «Теперь мы, слава Богу, один угол Черного моря уже имеем, а со временем, может быть, и все его иметь будем». На замечание, что сделать это будет трудно, Петр возразил: «Не вдруг, а помаленьку».

20 октября на заседании в Боярской думе было рассмотрено два вопроса: о заселении Азова русскими и о строительстве флота.

Бояре приговорили отправить в Азов 3 тысячи стрельцов с семьями из низовых (поволжских) городов и поселить там 400 калмыков.

По второму вопросу ограничились общим, но принципиальным решением: «Морским судам быть».

Конкретною решения были приняты на заседании Боярской думы 4 ноября 1696 г. Бояре приговорили патриарху и монастырям строить флот из расчета с 8 тысяч крестьянских дворов корабль, а боярам и дворянам из расчета с 10 тысяч дворов корабль. Купцы должны были совместно построить 12 кораблей.

Для строительства кораблей землевладельцы духовные составили 17 отдельных кумпанств (компаний), а светские —18. Для составления этих кумпанств помещики и вотчинники, имевшие 100 дворов и более, должны были приехать в Москву в Поместный приказ к 25 декабря 1696 г. под страхом конфискации царем их поместий и вотчин. Мелкопоместные же землевладельцы должны были внести по полтине со двора.

Первоначально планировалось построить кумпанствами 52 корабля, но затем это число увеличили до 71. Купцы тоже должны были построить на 6 кораблей больше, то есть 18. Несколько судов решили построить на государственные деньги.

В марте 1697 г. Петр уехал за границу, но строительство флота в Воронеже продолжалось. Вернувшись из-за рубежа в октябре 1698 г., Петр приехал в Воронеж и лично занялся строительством флота. Петр Алексеев стал официально занимать должность «адмиралтейской верфи баса» (мастера) и получил по ней денежное содержание от казны 366 рублей в год.

В ноябре 1698 г. в торжественной обстановке на Воронежской адмиралтейской верфи Петр заложил свой первый «государев» корабль — 58-пушечный «Гото Предестинация» («Божие предвидение»). Корабль имел длину 40 м и ширину 9,8 м.

Одновременно с Азовским флотом строилась его база на Азовском море — Таганрог, место для которого выбрал лично Петр сразу после взятия Азова.

Тем временем Австрия решила пойти на мир с турками. 3 ноября 1698 г. в Карловицах под Белградом была начата мирная конференция, на которой наряду с турецким и и австрийскими представителями был и русский посол П. Б. Возницын. 9 ноября на тайной встрече Возницы на с турецкой делегацией турки призвали русских последовать примеру царя Михаила, возвратившего ради дружбы с ними захваченный казаками Азов, и ради «приятства» вновь вернуть им Азов. Кроме того, турки настаивали на разрушении приднепровских городков, захваченных русскими в 1695 г. Возницын, в свою очередь, потребовал у турок Керчь, отчего османы пришли «в великое изумление».

На следующих встречах турки не упоминали об Азове, а русские — о Керчи. Спор возобновлялся лишь из-за приднепровских городков. Петр не хотел делать туркам, в общем-то, пустяковой уступки, но, с другой стороны, желал иметь свободные руки для войны со Швецией. Поэтому Возницын по указанию царя согласился лишь на двухлетнее перемирие с турками. Согласно этому перемирию Азов оставался за русскими, а вопрос о городках оставался открытым. Остальные же противники Турции 15 января 1699 г. подписали с ней Карловицкий договор. Австрийская империя сохранила за собой Славонию, Трансильванию, значительную часть Венгрии, без Темешвара, и часть территории к востоку от Тиссы} оставив туркам примерно одну треть их прежних владений в Венгрии и, соответственно, наконец-то утвердилась у ворот на Балканы. Польша вновь получила Подолию, Каменец и Западную Украину с участком территории к востоку от Тиссы, но ушла из Молдовы. Венеция вновь обрела Морею, остров Санта-Мауру, но уступила захваченные ею территории к северу от Коринфского перешейка.

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

24 мая Азовская эскадра пришла в Азов. В ее составе были корабли «Скорпион», «Благословенное начало», «Цвет войны», «Растворенные врата», «Святой апостол Петр», «Сила», «Безбоязнство», «Благое соединение», «Меркуриус», «Крепость», галеры «Периная тягота» и «Заячий бег», яхта, галиот и казацкие лодки. Сам Петр шел на корабле «Растворенные врата». По совету Возницына царь решил отправить в Стамбул чрезвычайного посланника думного дьяка Е. И. Украинцева, причем нетрадиционным путем посуше, а морем на 46-пушечном корабле «Крепость».

18 августа 1699 г. русская эскадра в составе 22 вымпелов появилась вблизи Керчи. Эскадра сопровождала корабль «Крепость», который должен был идти один в Стамбул. Турки под разными уловками не хотели пропускать корабли. Но дьяк Украинцев настоял на своем, и 7 сентября «Крепость» пришла в турецкую столицу. Посмотреть на чудо — первый неприятельский корабль, прибывший из Черного моря, — собрались тысячи людей. Пришли смотреть «Крепость» и великий визирь с султаном.

В ночь с 24 на 25 сентября произошел инцидент. Капитан «Крепости» голландец Петр Памбург встретил в Стамбуле знакомых французов и голландцев и пригласил их на корабль. Дело кончилось большой пьянкой. Под утро окосевший Памбург поднял экипаж по тревоге и приказал палить из пушек (хорошо еще, что холостыми зарядами). Днем 25 сентября к Украинцеву прибыл приближенный султана с протестом, потребовав смены капитана. По этому случаю Украинцев доносил Петру: «Салтаново-де величество ночесь испужался и из покоев своих выбежал от такой с твоего корабля капитанской ночной многой и необычайной пушечной стрельбы, и некоторые жены в сарае беременные от того страху и пушечной стрельбы младенцев повывергали, и за то-де салтаново величество на того капитана зело разгневался». С большим трудом Украинцеву удалось уладить сей казус.

На переговорах с Украинцевым турки вновь подняли вопрос о приднепровских городках. Поличному приказу царя Украинцев уступил.

3 июля 1700 г. Россия и Турция подписали Константинопольский договор, включавший в себя 14 статей. Первая статья устанавливала перемирие на 30 лет, а вторая предусматривала передачу приднепровских городков, предварительно разрушенных, Турции. Важное значение имела четвертая статья договора, оставлявшая Азов со всеми городками за Россией.

На родину Украинцев возвратился уже сухим путем. Корабль «Крепость» остался в Стамбуле и вернулся в Азов только в июне 1700 г., доставив домой 170 русских солдат, взятых в плен в 1695— 1696 гг.