Для удержания Азова и продолжения войны с Турцией 20 октября 1696 года Петр I во время «сидения с боярами в делах» в селе Преображенском предложил создать «флот или караван морской в 40 или веща судов состоящий». Боярская дума приговорила: «Морским судам быть, а скольким — о том справиться о числе крестьянских дворов, что за духовными и за всяких чинов людьми…» 4 ноября того же года на очередном «сиденье» великого государя с боярами было решено: «корабли сделать со всей готовностью, и с пушками, и с мелким ружьем, как им быть в войне, к 1698 году или прежде, а делать их так: св. патриарху и властям, и монастырям с 8000 крестьянских дворов корабль. С бояр и со всех чинов служивых людей с 10.000 крестьянских дворов корабль, гостям и гостинной сотне, черных сотен и слобод, беломесцам и городам вместо десятой деньги, которая с них собиралась в прошлых годах, сделать 12 кораблей со всеми припасами».

Так была создана законодательная и материальная основа крупных военно-морских сил на Азовском море, строительство которых положило начало российскому регулярному флоту. 1696 год можно с наибольшим основанием считать годом его рождения, учитывая значение не только законодательных актов, но и первого успешного боевого похода российского «морского каравана» и взятия Азова.

Первоначально для флота предполагалось построить 55 кораблей, 11 бомбардирских судов и брандеров. Светские и духовные владельцы крестьян, имевшие более 100 дворов, объединялись в «кумпанства» (компании), каждое из которых строило один корабль. 10 кораблей предстояло построить государю, 6 — патриарху, 5 — духовенству, 34 — боярам и дворянам, все бомбардирские и брандеры — городам.

Руководство всем делом сосредоточилось в «Царском шатре на Воронеже». Для непосредственного управления «кумпанствами» и адмиралтействами (верфями) Петр I назначил главу Владимирского судного приказа окольничьего А.П. Протасьева, получившего звание «адмиралтейца».

В Воронежском адмиралтействе и на 9 других верфях трудились тысячи крепостных крестьян, корабельные мастера, офицеры и матросы приглашались из-за границы. В 1694–1699 годах из Голландии, Англии, Дании, Швеции, Венеции прибыло до 170 одних только корабельных мастеров и подмастерьев, из которых около 80% составляли голландцы.

Однако уже в 1697 году Петр I направил за границу для обучения кораблестроению и навигации 60 молодых дворян, а вскоре и сам в составе Великого посольства, вместе с ближайшими помощниками, поехал учиться морскому делу. В 1697–1698 годах царь постигал практику кораблестроения в Голландии, теорию — в Англии, получил аттестат корабельного мастера, привезя в Россию не только знания и навыки, но и модели кораблей, книги, приборы и инструменты.

С 1698 года первых российских моряков обучал в своей «навигацкой школе» на реке Миус уроженец берегов Адриатики М. Меланкович. В августе 1699 года в Москве начал преподавание навигации и астрономии приглашенный Петром I воспитанник Эбердинского университета Генри (Андрей Данилович) Фарварсон (умер в 1739 г.).

14 января 1701 года в столице, в Сухаревой башне, указом Петра было основано первое в России высшее светское учебное заведение — «Школа математических и навигацких наук», или Навигацкая школа. Профессором навигации и астрономии в школе стал А.Д. Фарварсон, математику преподавал Л.Ф. Магницкий, автор известного учебника по арифметике. Школа была рассчитана на 200 человек и выпускала навигаторов, которые после практики на флоте по экзамену становились морскими офицерами или штурманами, а также специалистов для армии и гражданской службы. Вначале Петру I пришлось загонять некоторых дворян в школу грозными указами, а в 1711 году в ней обучалось уже 500 учеников в возрасте от 15 до 33 лет.

К 1700 году «кумпанства» построили 134 различных корабля и судна, однако качество последних из-за поспешности постройки, низкой квалификации мастеров и финансовых злоупотреблений оставляло желать много лучшего. Указом от 20 апреля 1700 года строительство кораблей было полностью передано от кумпанства государству. Казнокрада А.В. Протасьева Петр I заменил Ф.М.Апраксиным, поставленным во главе нового Адмиралтейского приказа.

Федор Матвеевич Апраксин (1661–1728 гг.), родственник дома Романовых (брат царицы Марфы, жены царя Федора Алексеевича), был в числе первых сподвижников Петра I по созданию «потешных» войск и флота. С 1693 года в должности двинского воеводы и губернатора Архангельска он руководил там созданием новой верфи для морских судов, потом участвовал во втором Азовском походе и изучал морское дело в составе Великого Посольства. Проявил себя незаурядным администратором, а впоследствии полководцем и флотоводцем и с 1706 года возглавил российский флот. В 1700–1706 годах Ф.М. Апраксин непосредственно руководил строительством кораблей, адмиралтейств в Воронеже и Таврове, военного порта в Таганроге, где предполагалось устроить гавань для помещения 200 судов.

Вернуть Азов и вообще направить против России сколько-нибудь значительные силы Турция не могла: она увязла в войне на западе империи. Несмотря на моральную поддержку со стороны Франции, которая даже провела военную демонстрацию против австрийцев на Рейне, османам не удалось добиться успехов. Сказалось качественное превосходство войск союзников по «Священной лиге».

Решающее сражение войны произошло в сентябре 1697 года при Зенте, у реки Тисы. Войско султана было разгромлено австрийской армией с потерей до 30 тысяч человек только убитыми. Погиб и великий везир, а сам Мустафа II едва спасся бегством.

В октябре следующего года в местечке Карловицы (Славония) собрался конгресс для заключения мира. Посредниками выступили представители Англии и Голландии, объединенных тогда одной короной (голландский штатгальтер Вильгельм Оранский был одновременно и английским королем — Вильгельмом III).

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

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

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

Война со «Священной лигой» обнаружила значительное ослабление военной мощи Османской империи. Карловицкий конгресс 1699 года знаменовал переход турок-османов от наступления на Европу к обороне. Турция на сей раз не получила не только дани либо контрибуции, как в предыдущие войны, но должна была отдать часть завоеванных ею прежде территорий. В то же время на конгрессе обнаружилось враждебное отношение европейских держав к России, что, понятно, вызвало большое недовольство Петра I. Все это в сочетании с ограниченными результатами Великого посольства 1697–1698 годов побудило царя к первоочередному разрешению балтийской проблемы.

Для этого требовалось обезопасить южные границы, т. е. добиться не перемирия, а прочного мира с Турцией. Успех переговоров мог быть обеспечен солидными аргументами — сильными армией и флотом. Если османская армия была серьезно потрепана союзниками, то флот неудачливого полководца султана Мустафы II в количественном отношении выглядел довольно внушительно.

В 1698 году, накануне переговоров в Карловичах, в составе султанского флота были вооружены:

— эскадра Мраморного (Белого) моря под командованием Хюсейн-паши (капудан-паша) — 21 корабль («галион») и 32 больших и средних парусно-гребных судна (галеры, «фрегаты»);

— эскадра Азовского моря под командованием Али-паши (в Керчи) — 4 корабля и 41 разного рода парусно-гребное судно (галеры, «фрегаты», «скампавеи»);

— Днестровская эскадра под командованием Мустафы-бея — 80 различных парусно-гребных судов.

О комплектации эскадры Азовского моря известно, что на каждом корабле насчитывалось по 450 человек команды, на больших 25-баночных галерах — по 150,18-баночных «фрегатах» — по 80, на 12-баночных «скампавеях» — по 35 человек, очевидно, без гребцов.

Поскольку Петр I не собирался вести военные действия после заключения перемирия, а передвижения армии могли вызвать негативную реакцию турок, то он выбрал в качестве аргументы дипломатии вновь построенный флот. Царь задумал вывести флот в Азовское море, провести демонстрацию у Керчи — показать флаг и направить посольство в Константинополь на военном корабле.

После смерти Ф.Я. Лефорта (в 1699 г.) общее руководство флотом возглавил генерал и адмирал Федор Алексеевич Головин (1650–1706 гг.), особо доверенное лицо из ближнего окружения Петра I. Отличившийся ранее на дипломатическом поприще, Ф.А. Головин был также поставлен во главе Приказа воинского морского флота, Посольского приказа, а с 1701 года одновременно осуществлял общее руководство Навигацкой школой. Он стал первым кавалером вновь учрежденного Петром I ордена Св. Андрея Первозванного (1699 г.) и первым российским генерал-фельдмаршалом.

В 1700 году в Воронеже был спущен на воду 58-пушечный корабль «Гото Предестинация» («Божье Предвидение»), спроектированный на основе лучших английских достижений и заложенный (в 1698 г.) самим Петром I — «корабельным мастером Петром Михайловым». Этот корабль (длина 36 м, ширина 9,5 м, глубина интрюма 2,97 м) строился исключительно россиянами под руководством царя, Федосея Скляева и Лукьяна Верещагина, и считался лучшим на флоте. На деках «Предестинации» были установлены 26 16-фунтовых и 24 8-фунтовых орудий, на баке и юте — 8 3-фунтовых орудий.