В конце февраля 1697 года Апраксин покинул Архангельск, царь взял его в вояж по Европе. «Фёдор Матвеевич, — как пояснил историк П. Белавенец, — сопутствовал государю заграницу и в Амстердам, учился вместе с ним кораблестроению». Но недолго пробыл там Апраксин. Царь отправил его на верфи в Воронеж, по-новому ладить суда для Азовской флотилии. В Англии царь выучился азбуке математических расчётов для конструирования кораблей. Нанял там мастеров, сведущих в этом деле, и послал в Воронеж.
На Воронежских верфях опытный в судостроении Апраксин сразу заметил непорядок. Любил он, как истинный мореход, порядок, честность в поступках, бережливость. На верфях всё было не так. Приказчики воровали, глядя на них, работники трудились вполсилы, многие ударялись в бега.
Присматриваясь к строительству «кумпанских» и казённых судов, Апраксин возмущался, пока про себя. Приписывали к строительству тысячи людей, а трудились сотни, на припасы отпускали большие деньги, а такелаж поставляли гнилой. Главный распорядитель на верфи, адмиралтеец Протасьев, смотрел на воровство сквозь пальцы. Доносительство не было в характере Апраксина. Он занялся делом. К тому же царь возвёл его в подполковники гвардии Семёновского полка и отправил в Азов обустраивать первую морскую силу России, Азовскую флотилию, готовить новую базу в Таганроге. Азовское море весной 1699 года окуталось пороховым дымом, салютовали русские корабли. Из Воронежа прибыла эскадра кораблей. Пётр готовил к отправке в Стамбул посольство Украинцева на 52-пушечном корабле «Крепость». На Керченском рейде «Крепость» появилась в сопровождении эскадры.
Наместник султана всполошился, запаниковал. Как так? Чёрное море принадлежит султану? Кто позволил русским? Откуда у них столько кораблей?
На рейде в Керчи в сонной тишине дремала на якорях турецкая эскадра.
Пётр пошарил трубой вдоль линии турецких кораблей, подозвал Апраксина:
— Вишь, второй с краю — ихний капудан-паша, флагман. Пойдёшь к нему с визитом. Скажешь, «так и так, русская эскадра мирная, провожает своего посла к султану».
Потом адмирал Фёдор Головин утихомирил наместника Муртозу-пашу: «Крепость», мол, корабль мирный, с добрыми намерениями плывёт в Константинополь»...
Вернувшись в Воронеж и обнаружив лихоимство на верфях, зимой 1700 года Пётр назначил Апраксина вместо проворовавшегося Протасьева. Царский указ гласил:
Вскоре началась Северная война со шведами, и под начало Апраксина перешли все новые верфи на Балтике — на Сяси, в Олонце и Санкт-Петербурге.
Адмиралтейцу Пётр подчинил новый Адмиралтейский приказ. Отныне Апраксин отвечал за всё корабельное строение на Руси. Зимой он обычно руководил работами на всех верфях, а летом открывал морскую кампанию Азовской флотилии. Кроме Воронежа, военные суда для флотилии строили на новых верфях в Ступине, на Хопре, в Чижовке, Павлове и других местах. За время правления Апраксина на всех этих верфях было построено около сотни боевых судов, в том числе не один десяток линейных кораблей. Одним из первых линкоров Апраксин вместе с царём спустил на воду 58-пушечную «Предистинацию». Это был первый корабль, построенный по чертежам царя русскими умельцами.