Из Сремски-Карлович Возницын выехал домой 24 января. Накануне он писал Ф.А. Головину и Л.К. Нарышкину о наболевшем. Его «беспокоят» южные соседи, он не верит ни туркам, ни татарам. Ссылаясь на то, что турецкие послы просили послать гонца от царя в Стамбул с известием о перемирии, Возницын предложил воспользоваться удобным случаем. Взятие Азова — это только начало. А выход из Азовского моря закрыт, так как Керченский пролив, через который могли пройти российские корабли, был занят османами. Зная, что турки обеспокоены работами русских на Азове, дипломат советует показать мощь русской военной силы. Возницыну известно: в Порте уверены в своем превосходстве на Черном море. Поэтому, по мнению Возницына, нужно отправить дипломатического курьера, лучше человека незнатного, но с умом, на военном корабле в Стамбул да проводить всем флотом до Керчи.
18 июня Возницын прибыл в Азов. Петр I внимательно расспросил посла. Сам царь готовился к большому событию. В 1698 году в Азове было открыто первое мореходное училище. В августе 1699 года Петр I вместе с Ф.А. Головиным — командующим первым в России Азовским флотом — совершил учебный поход в Керченский пролив. Тогда же на 46-пушечном корабле «Крепость» для встречи с царем был доставлен Е.И. Украинцев, на протяжении десяти лет возглавлявший Посольский приказ, Для заключения мирного договора с Турцией в Порту по совету Возницына отправили делегацию во главе с думным советником Е.И. Украинцевым и думным дьяком И. Чередеевым. Решая вопрос о перемирии на Юге, Россия продолжала готовиться к большой войне со Швецией. В августе 1699 года московиты подписали договор с Данией, а в ноябре — с Польшей.
5 августа из Таганрога отплыла эскадра, состоящая из 10 больших кораблей, двух галер, двух галиотов, четырех стругов с казаками под командованием Ф.А. Головина. Пройдя 20 верст, эскадра остановилась из-за разразившейся бури. Вернулись в Таганрог. 14 августа с попутным ветром поплыли во второй раз. 18 августа подошли к Керчи, дали салют и встали посреди Керченского пролива. С визитом к керченскому адмиралу Гасан-паше отправили Ф.М. Апраксина. По свидетельствам современников, Федор Матвеевич не отличался выдающимися способностями, но был исполнителен, усерден, имел веселый и добрый нрав. Умер Федор Апраксин бездетным, завещав движимое и недвижимое имущество родственникам и благодетелям. На том месте, где сегодня стоит Зимний дворец, стоял принадлежавший ему дворец на Неве. Позже, уже после смерти Петра I, Апраксин лично просил Петра II принять дом ко Двору Его Величества.
Перепуганный турецкий военачальник послал людей узнать, в чем причина появления русских военных кораблей, Турки, подплыв на лодках к русской эскадре, внимательно изучили и обшивку кораблей, и из какого дерева построены корабли. А русские матросы рассматривали Керчь. Крепость была небольшой: 5 башен и маленькие дома, один над другим, построенные по-татарски. Гарнизонный комендант пытался задержать отъезд русского посла в Стамбул. Предлагали ехать по суше, потому что, дескать, Черное море опасно, а из Керченского пролива нет выхода, потому как преграждает путь большому кораблю камень. Русский лоцман, которого капитан корабля отправил на разведку, доложил: камня нет, но есть скала, ее можно обойти. От царя пришел приказ — эскадре вернуться в Таганрог, а послу отплыть в Стамбул, В Порте, получив известие, были напутаны появлением русского флота, поэтому турки решили засыпать Керченский пролив и построить ряд небольших крепостей на перешейке. Позже от идеи засыпать пролив они отказались.