Около половины июня весь флот направился в Азовское море. Царь, дождавшись крепкого западного ветра, который поднял воду в донских гирлах, с искусством опытного лоцмана вывел корабль за кораблем из донского устья в открытое море. Собственноручным письмом он поздравил своих сотрудников, оставшихся в Москве, с благополучным выходом флота в море. По случаю происходивших у Таганрога последних приготовлений к морскому походу Крюйс писал: «Мы принялись за килеванье, конопаченье и мазанье кораблей с такою ревностью и с таким проворством, как будто на адмиралтейской верфи в Амстердаме. Его величество изволил сам работать неусыпно топором, теслом, конопатью, молотом, смолою гораздо прилежнее и исправнее старого и хорошо обученного плотника». По вечерам Петр в эти дни был обыкновенно занят составлением подробной инструкции для посла Украинцева. Главные требования России, о которых должен был заявить русский посланник в Константинополе, состояли в окончательной уступке Азова России и в безусловном прекращении всякой годовой дачи татарам
В полдень 5 августа из Таганрога отплыла эскадра из десяти больших кораблей, двух галер, двух галиотов и четырех стругов с казаками. Командовал ею опытный дипломат Ф. А. Головин, получивший звание генерал-адмирала. В морских делах он был так же сведущ, как и его предшественник в этом звании – Лефорт. Но так, очевидно, было удобнее Петру, который любил вершить дела сам, оставаясь при этом в тени. И в данном случае он был просто капитаном Петром Михайловым.
Поход в Керчь по всем признакам начинался неудачно. Эскадра отошла от Таганрога всего верст на двадцать, как разразилась сильная буря. Пришлось стать на якорь и простоять двое суток, качаясь на волнах, занятие не слишком приятное, если учитывать, что азовская качка неприятная: волна мелкая, но частая – корабль с борта на борт швыряет, внутренности у неопытных выворачивая. Не успели привыкнуть к морской стихии мужики российские, от сохи оторванные. Царь спуску никому не давал, о поблажках и думать не приходилось. Страдали животами матросики, да терпели…
Не только людям, но и снастям, и парусам досталось, да и мачтам – тоже. Пришлось возвращаться в Таганрог и ждать погоды еще две недели, да ремонт вести.
Наконец-то, в полночь 14 августа подул сильный попутный ветер. Петр дал сигнал к отплытию, сам он командовал кораблем “Отворенные врата”.Если бы корабли российские распустили все паруса, то на следующую ночь были бы уже в Керчи. Но старый моряк вице-адмирал Крюйс, прослышавши про коварные мели Азовского моря и Керченского пролива, посоветовал поставить только один парус. Поэтому двигались медленно, с остановками, с промерами дна и только 18 августа увидели "высокую землю Керченскую".
Это был великий день России. Русская эскадра стала посреди Керченского пролива. Четыре турецких корабля осторожно прижались к крепости. А крепость маленькая всего пять башен. Петр одним взглядом оценил ее состояние. Стены некрепкие и местами развалились. Это не Азов, который так трудно дался русским воинам. Разленились турки, ожирели от бездействия. А город Керчь то каков? Дома однотипные, с плоской татарской крышей, один над другим лесенкой к горе Митридат прилепились. Деревьев совсем нет. Только два десятка мечетей над городом возвышаются.
Для пущего эффекта флагманский корабль «Крепость», приближаясь к Керчи, отсалютовал семью залпами. К адмиралтейскому салюту присоединилась вся русская эскадра, и началась пальба из всех пушек. Туркам ничего не оставалось делать, как отвечать на приветствие, хотя какая уж тут радость – страх один: нежданно-негаданно русская эскадра нагрянула. Зачем? Как она вообще очутилась в Азовском море?
Тем временем на шлюпке под белым флагом к турецким властям прибыл Ф.М. Апраксин с поручением известить о прибытии русского флота и поздравить. Делать нечего, в ответ на визит Апраксина турецкий адмирал Гасан-паша прислал своих людей. Они стали расспрашивать адмирала Головина о причинах прибытия столь большого числа военных кораблей. Реакцию турок, видимо, хорошо передает запись Крюйса: "Ужас турецкии можно было из лица их видеть". Они никак не могли поверить, что эти корабли построены в России и на них русские люди. Но еще больше их поразило известие, что русский посол на военном корабле намерен отплыть в Константинополь.
До поздней ночи вокруг русских кораблей шныряли турецкие лодчонки. Одни смолу с обшивки соскребали, чтобы посмотреть, из какого дерева корабли построены. Другие дивились на матросские учения, которые приказал проводить Петр на виду турок и татар. А третьи устроили настоящий восточный базар – торговали всем, чем попало: и красочной с расписными узорами тканью, и диковинными фруктами, и овощами, охотно беря взамен московские ефимки.