Уже в 1775 году, когда Екатерина II Потемкин праздновали победу над Турцией в Москве, князь подружился с греческим монахом Евгением Булгарисом, которому предстояло обеспечить «богословскую поддержку» греческого проекта. 9 сентября 1775 года Екатерина, по внушению Потемкина, назначила Булгариса архиепископом Херсона и Славянска, когда этих городов еще не существовало. Херсон, названный в честь греческого Херсонеса, родины русского православия, виделся еще только бурному воображению Потемкина.

Декрет Екатерины о назначении Булгариса архиепископом подчеркивал греческое происхождение православия и, возможно, был составлен Потемкиным, одним из первых действий которого по занятии должности фаворита стало основание греческой гимназии. Теперь он поручил управление ею Булгарису. Потемкин хотел, чтобы архиепископ написал историю отношений древних скифов, греков и славян. Булгарис не выполнил этого пожелания, но зато перевел «Георгики» Вергилия и посвятил их «величайшему филэллинисту», сопроводив одой на строительство Херсона — новых Афин на Днепре.

Прослеживая зарождение греческого проекта, можно понять, как происходило сотрудничество императрицы и князя. «Мемориал по делам политическим», описывающий проект, составил в 1780 году секретарь Екатерины Александр Безбородко, однако считать его автором идеи означает не понимать взаимоотношений внутри триумвирата, который отныне станет определять внешнюю политику России.

Потемкин замыслил греческий проект еще до того, как Безбородко стал играть политическую роль: об этом свидетельствуют его письма, разговоры, покровительство Булгарису, наречение второго внука Екатерины Константином и основание Херсона в 1778 году. Записка Безбородко, несомненно, заказанная Екатериной и Потемкиным, представляла собой «техническое обоснование» идеи и описывала византийско-турецко-русские отношения с середины X века. Проект трактата с Австрией 1781 года, составленный Безбородко, показывает последовательность их работы: секретарь составлял текст на правой половине листа, а на левой Потемкин делал карандашом заметки, адресованные Екатерине. Потемкин формулировал общий смысл идеи, а Безбородко прописывал детали — что и дало последнему основание заявить после смерти светлейшего, что тот «был редкий человек, особливо на выдумки, лишь бы только они не на его исполнение оставлялися».

Первым шагом к исполнению греческого проекта должно было стать налаживание отношений с Австрией. Император Священной Римской империи и соправитель Габсбургской монархии, Иосиф II не отказался от плана овладеть Богемией — плана, породившего «картофельную войну». Он понимал, что для овладения этой областью, которая сделает габсбургские земли более цельными, ему необходима помощь Екатерины и Потемкина. Для этого Иосифу надо было отвлечь Россию от ориентации на Пруссию. Если по ходу дела Австрии удалось бы расширить свои границы за счет Османской империи — он был не против.

В течение долгих лет Иосиф и его мать Мария Терезия избегали контактов с Россией, считая Екатерину цареубийцей и нимфоманкой. Теперь Иосиф решил пойти против матери, в чем его поддержал канцлер, князь Венцель фон Кауниц, автор «дипломатической революции» 1756 года, помирившей Австрию с ее старым врагом, Францией. Кауниц инструктировал своего австрийского посланника в Петербурге: «Поставьте отношения с господином Потемкиным на дружескую ногу [...] Сообщите мне, каков он к вам сейчас».

22 января 1780 года Иосиф передал Екатерине через ее посла в Вене князя Дмитрия Голицына, что желал бы с ней встретиться.