Особливую аттенцию он уделял восстановлению Черноморского флота. Он паки вызвал своего управляющего Сэмуэля Бентама и других лучших кораблестроителей для создания гребной флотилии. Бентам его не подвел, как всегда. Галеры он превратил в канонерские лодки, установив туда гораздо более тяжелых орудий, нежели употреблялось допрежь. Командиром сей флотилии был назначен принц Нассау-Зиген. Он подружился с другим, недавно прибывшим, флотоводцем – Полом Джонсом, коий увлеченно рассказывал ему, как основал национальный флот в Америке и, как во время освободительной войны терроризировал британские берега. Императрица возлагала на американца большие надежды, несмотря на то, что адмирал Грейг и другие английские офицеры не захотели служить вместе с ним на Балтийском флоте, понеже воспринимали его, как предателя Британской короне. Потемкину надобны были талантливые моряки, и он, переименовав его на русских лад, как Павла Ивановича Джонс, поручил адмиралу командование парусной эскадрой из одиннадцати боевых кораблей. Гребная флотилия, большую часть которой составляли греки под началом полковника Мавромихали, оставалась у принца Нассау. На следующий же день после вступления контр-адмирала Джонса на должность, двадцатого мая перед Лиманом, под Очаковом появилась турецкая эскадра.
Чтобы вести успешно войну, русским надобно было овладеть Очаковом, но теперь, чтобы овладеть им, надобно было сначала уничтожить турецкий флот на Лимане.
После долгого топтания на месте у блокированного Очакова, в середине июня, князь Потемкин положил, что пришло время овладеть крепостью, но не штурмовать ее, а дабы сберечь силы и жизни солдат, осадить крепость по всем правилам военного искусства. Одновременно, он приказал выйти из Севастополя эскадре под командованием контр-адмирала Марко Войновича, главной задачей которого было не допустить турецкой эскадре оказать помощь осажденным.
На второй год войны, в самом начале лета, седьмого июня русскими был дан бой турецкому флоту, коий возглавлял алжирец Эски-Хасан-паша, прозванный «Крокодилом морских битв». Бентам, Джонс, и Нассау-Зиген ударили так, что флот турок стал беспорядочно отступать и, чтоб остановить их, Хасан-паша стрелял по своим, но ничего не мог поделать. Контр-адмирал Панайоти Алексиано, кавалер двух Георгиевских крестов, грек по национальности, находясь на борту флагмана – линейного корабля «Св. Владимир» – эскадры контр-адмирала Поля Джонса, не будучи командиром, фактически командовал парусной эскадрой. По его совету матросы успешно вели бой, вся их надежда была на него. Они считали, что сам Бог помогал им с оным греком – командиром.
Первого июля, Нассау-Зиген уничтожил остатки турецкого гребного флота под самыми батареями Очакова. После восьмичасового боя были сожжены два фрегата, четыре галеры и мелкие суда, четыре судна взяты в плен.
Новость о победе над турецким флотом доставил Потемкину граф де Дама, сообщивший такожде, что за два дня сражений, турки потеряли десять кораблей, пять галер, три тысячи человек убитыми и более полутора тысяч – пленными. Русские потеряли один фрегат, восемнадцать человек убитыми, и семьдесят ранеными. Де Дама застал Главнокомандующего в обществе принца де Линя. Узнав о победном исходе сражения, князь был вне себя от радости. Обхватив высокого и худощавого графа, он едва не задушил его в своих мощных объятьях. Отпустив его, он обернулся к де Линю:
– Что я вам говорил? – крикнул он, обнимая его. – Не чудо ли сие? Да, я – баловень у Господа Бога!
Позже, выслушав подробности морской битвы, он, ликуя, воскликнул: