Потемкин оказался непреклонен: Завадовский должен был уйти. Летом 1777 года после менее чем восемнадцати месяцев пребывания в качестве фаворита, он ушел, ожесточенный и безутешный, приняв прощальный подарок императрицы – восемнадцать тысяч рублей – и заперся в своем имении в Украине. Той же осенью Екатерина предприняла вялую попытку вернуть его, но в 1777 году разразился политический кризис. К тому времени Потемкин как наместник управлял южной частью империи Екатерины, и его поддержка была слишком важна для нее, чтобы рисковать ею из-за перипетий личной жизни. Завадовский жил вдали от двора в течение трех лет и вернулся в Санкт-Петербург в 1780 году, когда получил назначение в качестве тайного советника. В 1781 году он стал директором государственного банка, который был организован на основании предложенного им же плана. Впоследствии он стал сенатором и закончил карьеру в должности министра народного просвещения при внуке Екатерины Александре I.

Новые отношения между Екатериной и Потемкиным давали им свободу в выборе сексуальных партнеров, но позволяли сохранять при этом нежные чувства друг к другу и тесный политический союз. Екатерина часто скучала без него: «Сгораю от нетерпения увидеть вас, мне кажется, что мы не виделись уже год. Целую вас, мой друг. Возвращайтесь счастливым и в добром здравии, и мы будем любить друг друга… Целую вас и так хочу увидеть, потому что люблю вас всем сердцем». В своих письмах она также сообщала ему, что ее новый фаворит – кем бы он на тот момент ни был – шлет ему выражение любви и признательности. Она также заставляла своих любовников писать ему. В основном это были льстивые заверения в том, как они скучают, восхищаются или даже преклоняются перед ним. Молодые люди подчинялись, поскольку они знали, в сравнении с влиянием Потемкина на Екатерину, их собственное – являлось ничтожным.

Между тем Потемкин по-своему продолжал любить Екатерину. Его физическая страсть угасла, но привязанность и верность ей остались. В то же самое время он вступал в связи с различными женщинами. Среди его увлечений были три из пяти его племянниц: Александра, Варвара и Екатерина – дочери его сестры Марии Энгельгардт.

Варвара первой привлекла внимание дяди. Золотоволосая, кокетливая и требовательная, она в свои двадцать лет знала, как вертеть князем, которому на тот момент было уже тридцать семь. Потемкин предпринимал титанические усилия, чтобы понравиться ей. Его письма к ней были гораздо более пылкими, чем те, что он писал Екатерине:

«Варенька, когда я люблю тебя до бесконечности, когда мой дух не имеет, опричь тебя, другой пищи <…> Прости, божество милое <…> Прощайте, сладость губ моих <…> Ты заспалась, дурочка, и ничего не помнишь <…> Я, идучи от тебя, тебя укладывал и расцеловал и одел шлафроком и одеялом и перекрестил <…> Варенька, моя жизнь, красавица моя, божество мое; скажи, душа моя, что ты меня любишь, от этого я буду здоров, весел, счастлив и покоен; моя душа, я весь полон тобой, моя красавица. Прощай, целую тебя всю».