В летний, Петров день, года 1783, через Московскую заставу столицы маршировало странное войско. Первым твёрдо ступал флотский офицер, а за ним поротно с офицерами семь сотен матросов и три тысячи мастеровых. Ушаков, командир линейного корабля, строящегося в Херсоне, вёл походом туда свой экипаж и работных людей. На юге сооружали верфи и корабли для зарождающегося Черноморского флота.
Колонна шла ускоренно, привалы только для ночёвок. Первый роздых в Первопрестольной. Матросов разместили по квартирам, и, чувствуя слабину, многие перепились, устроили мордобой с московскими домоседами. Из Москвы их спешно вывезли в поле на телегах. В Херсонской степи сделали последний привал, с юга потянуло дымком. Ушаков послал квартирмейстера лейтенанта Петра Данилова.
— Отрапортуешь вице-адмиралу Клокачеву о прибытии команды, осмотри квартиры и мигом возвращайся.
Данилов прискакал на взмыленной лошади:
— Так что, ваше превосходительство, в Херсоне чума, кругом на улицах усопшие, вице-адмирал советует размыслить, работы на верфях в затишье, квартир пока нет.
Нахмурившись, Ушаков долго молчал, расхаживая по палатке.
«У меня высочайший указ строить корабли. Как наилучше исполнить?» — думал он.
— Значит, так. — Внезапно остановившись перед Даниловым, он чеканил фразы: — Корабли будем ладить по указу её величества. Людям нынче же рыть землянки подле Херсона, там будем жить. Каждодневно окуривать дымом людей и жильё, хворых отделять немедля в карантин.
Ушаков действовал на два фронта — воевал с чумой, строил корабли. Осенью скончался от чумы Клокачев, на смену ему прибыл вице-адмирал Сухотин. Он сразу выделил действия Ушакова в донесении графу Чернышёву:
Адмиралтейств-коллегия не раз благодарила Ушакова. 1 января 1784 года он получил чин капитана 1-го ранга, награждён за борьбу с чумой первым орденом, Святого Владимира IV степени, назначен командиром построенного под его присмотром линейного 66-пушечного корабля «Святой Павел». Орден Ушаков не успел получить, и весной 1785 года «Святой Павел» покинул верфи Херсона.
Ушаков руководил его проводкой по Днепру от Херсона до Глубокой пристани, где были произведены постановка мачт, вооружение такелажем и парусами, и установка артиллерии. Подготовив корабль к плаванию, совершил переход Днепровским лиманом к Кинбурну и далее Чёрным морем в Севастополь.
Знойным августовским днём 1785 года линейный корабль «Святой Павел» под командой капитана 1-го ранга Ушакова отдал якорь в Ахтиарской бухте у небольшого мыска. Вдаль уходила бирюзовая синь прекрасной гавани, направо вытянулась ещё одна бухта, поменьше, но довольно вместительная и уютная. Крутые склоны высоких курганов, поросшие диким лесом и кустарником, спускались к самому урезу воды. Ушаков вместе с командой своего корабля заложил первые камни в основание города русской морской славы. Пройдут десятилетия, и этот мысок, уже одетый в камень, сохранит название «Павловский», потому что «Святой Павел» облюбовал здесь себе постоянное место якорной стоянки. Белокаменные матросские казармы поднимутся на склонах холмов, и их нарекут ушаковскими, по имени командира отряда матросов, строивших эти здания...
Забот вскоре прибавилось. Увидев однажды Ушакова, светлейший Потёмкин, отлично разбиравшийся в людях, держал его на примете до конца дней своих. Л начальству Ушакова не нравилось такое внимание. Командовал эскадрой капитан 1-го ранга Марк Войнович. В своё время на Каспии попал он в плен к персам, стал ещё более боязлив. Его тоже коробила любая инициатива Ушакова.
Со времён борьбы с чумой в Херсоне грызла Войновича мелкая зависть.
Ушаков готовил к войне не только корабль, его вооружение и снаряжение. Он думал о тех, кто движет кораблём. Учил терпеливо и одинаково и офицеров и матросов. Где надо, подскажет, с нерадивого взыщет жёстко.
Однако заботу о себе служители видели не только в добрых харчах и положенном довольствии.