Спиридов, как известно, позднее получил назначение на эскадру, направляющуюся в Средиземное море, но на первом этапе энергично участвовал в делах Южного флота. Сенявин же столкнулся с запустением, ветхостью, неподготовленностью верфей, с отсутствием карт Дона и побережья, лоцманов на реке. Не было леса, железа, полотна и, главное, строителей. Адмиралтейств-коллегия срочно посылала на юг инженеров, корабельных мастеров, офицеров, топографов и приходила «в рассуждение за всем своим старанием» к неутешительным выводам о том, что Дон почти непреодолим для больших кораблей по причине мелководности мест, протянувшихся поперек кос, незаметных отмелей. Тогда и решено было «изобрести» новые плоскодонные суда с малым количеством пушек. Придя к такому решению, Коллегия повелела: в январе 1769 года «Новоизобретенных по приложенной ведомости судов… приказано построить на сто тысяч рублей, а сколько какой величины числом — оное имеет Коллегии определить по своему рассуждению, смотря на пользу и выгодность их».
Так стали строиться первые 12 «новоизобретенных» судов, так стал воссоздаваться Азовский, а впоследствии Черноморский флот России.
Загоняя лошадей в зимнюю январскую стужу, мчался из Петербурга в Воронеж в январе 1769 года контр-адмирал Сенявин. В Москве он накричал на чиновников, требуя согласно распоряжению Адмиралтейства отправить немедленно работников, рекрутов, плотников в Воронеж. В губернском городе он не задержался и помчался в Тавров. Было ясно, что ничего для создания флота не готово. Хваткий контр-адмирал, обнаружив недостроенные прамы, собрал артель плотников и бросил ее на их достройку, сам же ринулся в Таганрог.
Генерал-губернатор Маслов отговаривал его от этой небезопасной затеи — степь бороздят отряды турок и татар.
— Мне флот строить надобно, а не ждать, пока война кончится, — бросил ему из кибитки Сенявин.
Проскакав по вьюжной степи с небольшим конвоем, Сенявин утром 14 февраля был в Таганроге и сразу же приступил к промерам в гавани. Для «новоизобретенных» судов она годилась, для других нет. Поэтому пока он решил строить корабли в Павловске и Искорецке, Таврове и Новохопёрске. Екатерина II интересуется, как идут дела, способны ли создать все-таки флот там, в степях. В мае она пишет Сенявину:
«Алексей Наумович! Посылаю вам гостинцы — которые до тамошних мест принадлежат: 1) разные виды берегов Черного моря, даже до Царьграда; 2) Азовское море; 3) корабль на Воронеже деланный и на воду там же опущенный. Оные, как я думаю, будут вам приятны и, я думаю, может быть, сверх того и полезны. Пожалуй, дайте мне знать, ловко ли по реке Миусу плыть лесу в Троицкое, что на Таганроге, и ваше о том рассуждение, также есть ли по Миусу годные леса к корабельному строению? Я чаще с вами в мыслях, нежли к вам пишу. Пожалуй, дайте мне знать, каковы выдуманные суда по вашему мнению могут быть на воде, и сколько надобно, например, времени, чтоб на море выходить могли».
Сенявин внимательно рассмотрел чертежи и с горечью сказал Селиванову:
— Великое б мое было счастье, если б я не только таковой величины корабли, как в этом чертеже обозначены, но хотя бы до 32 с большим калибром пушек судов до 10 иметь мог, коим… не только доказал бы мою службу, но и не помрачил бы славы русского оружия.
Сенявин понимал, что на Дону надо строить основной костяк судна, а довооружать его в Таганроге, иначе оно не пройдет по Дону, да, кроме того, одними «новоизобретенными» кораблями не поможешь в овладении Крымом, им нужно подкрепление галер, и в таком случае «не одна восточная часть, но и весь Крым долженствует, содрогнувшись, передать себя в монаршье покровительство, где известны три места: Еникаль, Керчь и Кефа будут служить к строению больших кораблей».
Это уже была программа дальновидного политика и стратега, не сомневающегося в том, что русский флот прочно выходит на Азовское и Черное моря.