Потемкин, с детства мечтавший о завоевании Греческого моря, сочинил проект, который чрезвычайно заинтересовал императрицу. Цель этого проекта состояла в изгнании турок из Европы и образовании на тепленьком местечке, освободившемся после Оттоманской Порты, православного Греческого царства. Править этим царством должен был великий князь российской императорской фамилии. О создании православного Греческого царства мечтал еще Петр Великий. В донесениях английский посол Гаррис с сожалением сообщал своему королю, что Потемкин буквально «заразил» императрицу идеями об «учреждении новой Византийской империи». Русские корабли в Средиземном море внушали «Владычице морей» – Великобритании – вполне понятный страх.
В реализации Греческого проекта должна была принимать участие и Австро-Венгерская империя. Петербург и Вена намеревались изгнать турок из Европы, восстановить Византию, образовать из Молдавии и Валахии буферное государство Дакию и передать западную часть Балканского полуострова Австрии. В мае 1780 года состоялось свидание австрийского императора и Екатерины в Могилеве, и русско-австрийский союз объявил миру о своем рождении. Военная колонизации Новороссийского края, фантастическое по масштабам переселение в Причерноморье русских и балканских колонистов и, конечно, создание Черноморского флота – вот краеугольные камни, положенные в основу Греческого проекта.
Частью Греческого проекта должно было стать основание причерноморских и крымских городов: «города победы» – Никополя (город Победы), нового Херсонеса-Херсона, города Славы – Севастополя, «Объединяющего града» – Симферополя, Одессы, названной в честь древнегреческого Одессоса… В херсонском соборе Святой Екатерины государыня намеревалась короновать своего внука Константина – будущего императора Византии.
На Днестре был заложен Тирасполь («Тирасом» Днестр называли древние греки), на Кубани – Ставрополь («город креста»). Своей очереди ожидали причерноморские города – Овидиополь, Ольвиополь, Мариуполь и Николаев. В 1778 году на берегу реки Кильчень Потемкин заложил еще один город – Екатеринослав, призванный закрепить славу императрицы в освоении края.
По Кучук-Кайнарджийскому договору Крымское ханство признавалось независимым от Оттоманской Порты. На крымский престол вступил ставленник Петербурга хан Шагин-Гирей. Однако борьба вельмож, ориентированных на враждующие стороны – Россию и Турцию, превращала полуостров в пороховую бочку. В мае 1782 года турецкая партия избрала ханом брата Шагин-Гирея, Батыр-Гирея, и обратилась к Порте за помощью. В ответ Россия ввела свои войска в Крым. Мятеж удалось подавить. Ослабевшая Порта воздержалась от вооруженного вмешательства. После завоевания Крыма Потемкина стали называть князем Таврическим.