В 1699 г. в чине капитана Петр плавал в Азовском море, командуя кораблем «Отворенные Врата». В следующем году учредил Московскую математико-навигацкую школу, а еще через два года, в 1703 г., заложил Петербург, собственноручно сделав промер фарватера у о. Котлин и указав место для постройки крепости. Начиная с 1713 г. он посылает мореходов и геодезистов для исследования Охотского моря и Курильских островов.
Но это будет потом. А пока, вернувшись из Европы и находясь под впечатлением от увиденного в Англии и Голландии, у Петра возникает замысел постройки линейного корабля на российской верфи. Для этого он пригласил в Россию нескольких английских и голландских судостроителей. Но их прибытие задерживалось, и Петр решил его строить, не прибегая к помощи иностранцев, по русским чертежам, силами русских мастеров и из нашего материала. Нетерпение Петра имело веские причины — шла война с турками, войска осадили крепость Азов, но не могли ее захватить или принудить к сдаче, т. к. турецкий флот обеспечивал осажденную крепость боеприпасами и провизиею. На Азовском море нужен был свой флот, который мог бы противостоять турецкому. Для этого в Воронеже срочно была построена верфь, на которой стали строить первые боевые корабли для российского флота. Приступив к созданию регулярного военного флота, Петр ввел разделение кораблей по рангам, в соответствие с которым линейными кораблями считались корабли длиной в 40…55 м, трехмачтовые, вооруженные 45…90 орудиями. Фрегаты, соответственно, были длиной до 35 м, трехмачтовыми, с 28…44 орудиями
Первый линейный корабль был заложен 19 ноября 1698 г. на верфи в Воронеже. По воле молодого царя его назвали «Гото Предестинация», что по-латыни означает «Божие провидение». В работе над кораблем Петру помогал его соратник еще по строительству «потешной флотилии» Ф.М. Скляев и искусный плотник Л. Верещагин. Орудия для корабля также были отлиты в России на заводах Демидова.
«Предестинация» стала первым кораблем петровской эпохи, построенным «по английской методе». Ее корпус имел строго выверенные пропорции и плавные обводы, присущие кораблям северной Европы. Чертежи корабля делал сам Петр, взяв за основу чертежи английского корабля и внеся в них много изменений и новшеств. Так как корабль предназначался для плавания в мелководном Азовском море, Петр значительно уменьшил осадку судна, что потребовало поиска новых пропорций для обеспечения хороших мореходных качеств. В процессе постройки были введены существенные конструктивные усовершенствования. Киль корабля отличался особым > устройством крепления, изобретенным Петром и позволявшим сохранить водонепроницаемость корпуса в случае отрыва киля от удара о грунт. В иностранных флотах нечто подобное появилось только через 150 лет. До этого киль корабля изготовляли из одного массивного бруса. Петр I приказал изготовить его из двух брусьев, скрепленных между собой деревянными нагелями. В случае удара о грунт отвалился бы только нижний брус, само же судно осталось бы неповрежденным. Подобная конструкция была применена при строительстве судов в Англии лишь в 40-х годах XIX в.
27 апреля 1700 г. в присутствии высших чинов государства и иностранных послов богато украшенный позолоченными скульптурными украшениями 58-пушечный корабль был спущен на воду самим Петром I и вошел в состав Азовского флота. По этому поводу голландский посол в России Ван дер Гульст сообщал в Гаагу: «Будучи в Воронеже, мы видели спуск на воду очень красивого корабля, построенного царем с помощью русских мастеров. Ни один иностранный мастер не приложил руки к этому делу». Петр I был очень доволен кораблем: «Весьма красивый, зело изряден пропорцией, изрядного художества и зело размером добрым состроенный». «Гото Предестинация» славилась не только своей боевой мощью, она стала одним из первых произведений русского декоративного искусства в стиле барокко. Резьба на баке и корме, венки на пушечных портах были покрыты позолотой, а ставни портов и фальшборт изнутри окрашивались в огненно-красный цвет, контрастировавший с белыми парусами корабля.
По отзывам современников, «Гото Предестинация» обладала превосходной остойчивостью, хорошо всходила на волну и была самым быстроходным кораблем в азовской эскадре вице-адмирала К.И. Крюйса, в течение 10 лет сковывавшей враждебные действия Турции против России.
В 1700 г. началась война со шведами, отвлекшая внимание Петра на север, к Балтийскому морю. В дальнейшем все мероприятия были направлены на создание военного флота в Балтийском море. Начало войны ознаменовалось появлением шведской эскадры из 5 фрегатов и 2 галиотов в Белом море и нападением их на Архангельск, окончившимся неудачей — один фрегат сель на мель и был взят, равно как и оба галиота, остальные ушли. В 1702 г. была взята крепость Нотебург (Шлиссельбург), а в 1703 году крепость Ниеяшанц на Неве и заложен новый город — Петербург.