23 июня флот вышел в Таганрогский залив и после стоянки в Таганроге направился к турецкой крепости Керчь. В походе К. Крюйс при участии царя заснял северо- восточное побережье Азовского моря на протяжении почти 500 км и выполнил многочисленные промеры, показавшие глубины от 4,3 м до 19 м. Фактическое наличие таких глубин в корне противоречило представлениям географов того времени и высказываниям турецких моряков. Эскадра беспрепятственно подошла к Керчи, и турки были вынуждены допустить доставку российского посольства в Стамбул по Черному морю. Корабль «Крепость» был первым кораблем созданного в 1696 г. нового российского флота, совершившего плавание по Черному морю.
На обратном пути из Стамбула плавание «Крепости» по Черному морю прошло вполне благополучно, и в начале июня 1700 г. корабль прибыл в Таганрог. В донесении Петру, посланному из Стамбула 28 апреля, посол Украинцев писал, что он приказал капитану Памбургу на обратном пути зайти в Балаклаву и Кафу (Феодосию) и осмотреть подходы к этим портам.
Судя по атласу карт реки Дон, Азовского и части Черного моря, составленному Крюйсом и изданному в 1703—1704 гг., задание это было Памбургом выполнено. Более того, штурман «Крепости» поручик Христиан Отто составил пошедший в этот атлас черновой очерк Южного побережья Крыма от места расположения теперешнего Севастополя до Керченского пролива с указанием глубин моря на всем этом протяжении.
Значит, с борта «Крепости» были проведены первые в истории гидрографические исследования на Черном море с прибрежным промером глубин и описанием берегов. Плавание «Крепости» и проведенные замеры показали, что южнее Керчи есть большие глубины, а в центральной части моря нет мелей, как считалось до этого.
На протяжении всего XVIII в. Российское государство упорно добивалось свободы мореплавания по Черному и Азовскому морям и обеспечения безопасности южных областей Руси от нападения турок и татар Крымского ханства. В 1711 г. неудачный Прутский поход Петра I закончился миром с турками, по которому Россия возвратила им захваченный в 1696 г. Азов в устье Дона.
В 1735 г. императрица Анна Иоанновна начала новую тяжелую войну с Османской империей и Крымским ханством. В ходе боевых действий 2 июля 1737 г. русские войска под командованием генерал-фельдмаршала Миниха захватили турецкую крепость Очаков в Днепро-Бугском лимане. Для продолжения успешной борьбы с турками на побережье Черного моря необходимы были суда. Миних, докладывая императрице о взятии Очакова, просил:
В начале октября Сенявин встретился с командующим армией Минихом в Полтаве. В ходе встречи было решено, какие суда необходимо строить в Брянске и как сплавлять их к морю через Днепровские пороги. Миних доносил императрице:
Уже в царствование Екатерины II в конце 1768 г. Турция вновь объявила войну России. В 1769 г. Адмиралтейств- коллегия предписала контр-адмиралу Алексею Наумовичу Сенявину (впоследствии адмирал), сыну Наума Акимовича, возглавить Донскую экспедицию и начать строительство на донских верфях гребно-парусных судов для ведения боевых действий на Азовском море. Одновременно с этим он был произведен в вице-адмиралы.
Учитывая, что новые суда строились на реках, они по конструкции и размерам отличались от всех существовавших тогда классов боевых кораблей и их назвали «новоизобретенные корабли». При осадке не более 9 футов (2,75 м) эти почти плоскодонные двухмачтовые суда имели длину до 100 футов (30,5 м) и ширину до 28 футов (8,5 м). Они вооружались довольно сильной артиллерией: от 12 до 16 пушек среднего калибра.