С 1783 г. Ушаков служил в новых портах Черноморья: сначала в Херсоне (1783-1785 гг.), а потом (с 28 августа 1785 г.) - в Севастополе.
Эти населенные пункты громко именовались городами, хотя Херсону, когда Ушаков прибыл в этот поселок, было от роду пять лет, а Севастополю еще и того не было. В Херсоне служба была тяжелая. Ушаков много потрудился по борьбе с чумой, которая разразилась там как раз в первый же год его службы. К этому времени уже успела выявиться яркая черта Ушакова, сближающая его с позднейшими нашими замечательными флотоводцами: Лазаревым, Нахимовым, Макаровым. Мы имеем в виду заботу о матросе, о его здоровье, о гигиене на корабле, об общем благосостоянии команды, его неустанную борьбу против разворовывания казенных денег, ассигнуемых на пищу и одежду личного состава флота.
Ушаков выселил всех своих моряков далеко за город на все время, пока не утихла эпидемия. Все работы на несколько месяцев были прерваны.
Когда началась русско-турецкая война 1787-1791 гг., Ушаков еще на подчиненных ролях проявил себя талантливым боевым руководителем. Борьба предстояла нелегкая. Ведь эта война ничуть не походила на русско-турецкую войну 1768-1774 гг., которая тоже была трудная. Турки начали готовиться к реваншу тотчас же после Кучук-Кайнарджийского мира. Султан только тем успокоил свое духовенство (улемов), возбуждавшее недовольство в народе, что мир с русскими - это не мир, а лишь перемирие, передышка; и когда после нескольких лет мира Россия в 1783 г. присоединила Крым, то улемы уже совсем открыто и без препятствий со стороны властей предвещали войну с проклятыми гяурами и несомненное торжество правоверных. Усиленно строили корабли, укрепляли изо всех сил Измаил и другие крепости, набирали и обучали матросов. Да и внешняя дипломатическая обстановка складывалась для Оттоманской Порты благоприятно: к старому другу - Франции - прибавились новые друзья Полумесяца - Англия, Пруссия, Швеция, так что хотя австрийский император Иосиф II и стал на сторону Екатерины, но все-таки настроение в Константинополе было самое воинственное. А на море, где Австрия ни малейшей помощи русским оказать не могла, и подавно позволительным казалось рассчитывать на полный успех турецкого флота над еще только что созданным слабым русским флотом.
Не сразу засияла над Черным морем звезда Ушакова. Первый выход Ушакова в море в августе 1787 г. в эскадре графа Марка Войновича, где он, командуя в чине бригадира кораблем «Св. Павел», был начальником авангарда, окончился неудачей. В поисках турецкого флота эскадра была застигнута у румелийских берегов страшным продолжительным штормом. Один корабль погиб, другой без мачт в полузатонувшем состоянии был занесен в Босфор и здесь захвачен турками: остальные в сильно потрепанном виде вернулись в Севастополь и требовали продолжительного ремонта. В борьбе со стихией Ушаков проявил себя смелым и знающим моряком и, занесенный к кавказским берегам, все же благополучно довел свой корабль до базы.
3 июля 1788 г. на Черном море произошла первая «генеральная баталия» между обоими флотами, где Ушаков в той же должности начальника авангарда блестяще проявил свое тактическое искусство. Встреча противников произошла у острова Фидониси. Против семнадцати линейных кораблей (в том числе пять 80-пушечных) и восьми фрегатов турецкого капудана-паши Эски-Гасана русский флот имел два линейных корабля (оба 66-пушечные) и десять фрегатов. По силе артиллерии и количеству выбрасываемого в залпе металла турки были сильнее почти в три раза.
Но после ожесточенного трехчасового боя противник во избежание совершенного поражения вынужден был отступить и скрыться в беспорядке.