За умелые действия и проявленные при этом старания Феодор Ушаков был произведен в капитаны первого ранга и награжден орденом святого Владимира четвертой степени.
Трактатом между Россией и Турцией от 28 декабря 1783 года Крым был окончательно присоединен к России. И тогда же Екатериной II был издан указ об устройстве на южных рубежах новых укреплений, среди которых необходимо было выстроить и «крепость большую Севастополь, где ныне Ахтияр и где должны быть Адмиралтейство, верфь для первого ранга кораблей, порт и военное селение». В августе 1785 года в Севастополь из Херсона на 66-пушечном линейном корабле «Святой Павел» прибыл капитан первого ранга Феодор Ушаков.
11 августа 1787 года Турция объявила войну России. Для ведения боевых действий были развернуты две армии: Екатеринославская под предводительством генерал-фельдмаршала ГА. Потемкина-Таврического и Украинская генерал-фельдмаршала П. А. Румянцева-Задунайского. На первое время им предписывалось лишь охранять российские границы и только Севастопольскому флоту было велено действовать решительно. Вскоре произошла первая генеральная баталия.
Турецкий флот насчитывал семнадцать линейных кораблей и восемь фрегатов, а в русской эскадре, авангардом которой командовал капитан бригадирского ранга Феодор Ушаков, было всего два линейных корабля и десять фрегатов. 29 июня 1788 года противники обнаружили друг друга и, находясь во взаимной близости, старались занять выгодную позицию и сохранить линию баталии. Но 3 июля у острова Фидониси бой стал неизбежен. Турецкий флот всей мощью своей линии стал спускаться на русские корабли. И тут авангардный отряд Ушакова, «употребив старание и искусство», прибавил парусов и решительным маневром лишил возможности командующего турецким флотом Эски-Гассана охватить русские корабли и взять их на абордаж. Вместе с тем Ушаков отрезал от основных сил два передовых турецких корабля. Те, в свою очередь, обнаружив свое гибельное положение, не дожидаясь никакого сигнала, бросились спасаться бегством «с великой поспешностью». Эски-Гассан вынужден был пуститься вдогонку своим кораблям. Победа была за русской эскадрой.
Это сражение хотя и не имело существенного влияния на дела всей кампании, но оно было примечательно в другом. Впервые в открытом бою малочисленный русский флот одержал победу над превосходящими силами противника. Начальствуя только авангардом, Феодор Ушаков в действительности руководил боем всей эскадры, и его личная храбрость, искусное владение тактикой, выдающиеся качества командира и высокий духовный облик решили сражение в нашу пользу. Это была, прежде всего, духовная победа, в которой христианское самоотвержение исполнило силой воинское искусство. Вера в вечную жизнь, несомненное упование на помощь Божию и, следовательно, неустрашимость перед неприятелем – вот что было решающим во флотоводческом таланте Феодора Ушакова. По своему смирению и отсутствию тщеславия Феодор Ушаков в донесении не себе приписал успех, но отдал должное мужеству и стремлению к победе своих подчиненных: «Все находящиеся в команде вверенного мне корабля „Святого Павла“ господа обер-офицеры и нижних чинов служители каждый по своему званию определенные от меня им должности исполняли с таким отменным старанием и храбрым духом, что за необходимый долг почитаю отнесть им всякую за то достойную похвалу…»
Закончился первый год войны, в котором сокрушились турецкие морские силы, а молодой Черноморский флот одержал решительную победу, приведя Оттоманскую Порту «в чрезвычайный страх и ужас». Феодор Ушаков, получив чин контр-адмирала, был назначен в начале 1790 года командующим Черноморским флотом. Князь Потемкин писал Императрице: «Благодаря Бога, и флот и флотилия наши сильней уже турецких. Есть во флоте Севастопольском контр-адмирал Ушаков. Отлично знающ, предприимчив и охотник к службе. Он мой будет помощник». А в боевой инструкции князя Потемкина Феодору Ушакову говорилось: «Требуйте от всякого, чтоб дрались мужественно или, лучше скажу, по-черноморски; чтоб были внимательны к исполнению повелений и не упускали полезных случаев… Бог с вами! Возлагайте твердую на Него надежду. Ополчась Верою, конечно победим. Молю Создателя и поручаю вас ходатайству Господа нашего Иисуса Христа!»