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