А замена ему нашлась в лице Григория Александровича Потёмкина (1739–1791), который в 1762 году, в год восхождения Екатерины на престол, служил в конногвардейском полку вахмистром и принимал участие в перевороте тем, что вёл среди солдат пропаганду в пользу великой княгини Екатерины Алексеевны и вместе со своими солдатами в первых рядах присягнул императрице Екатерине II. В списках награждённых первоначально ему в качестве награды был назначен чин корнета, но Екатерина вычеркнула эту строку и собственноручно написала «капитан-поручик», повысив ему чин на три ранга Кроме того, он получил придворное звание камер-юнкера, 400 душ крепостных и серебряный сервиз.
Григория Потемкина Екатерина знала уже более двенадцати лет. Он давно нравился ей. И действительно, в молодости он был очень строен и красив, о чём свидетельствует его портрет того времени. В 1769 году Потёмкин отправился на Русско-турецкую войну, где проявил себя весьма мужественно: отличился под Хотином, участвовал в армии П. А. Румянцева-Задунайского в битвах при Фокшанах, Ларге и Кагуле. Из реляций полководца Румянцева-Задунайского Екатерине были известны мужество и храбрость Потёмкина, проявленные им на войне. Задумав отставку Васильчикова, она вступила с Потёмкиным в переписку и в 1773 году дала добро на пожалование его в генерал-поручики. В то время он сражался под стенами Силистрии, осаждённой русскими войсками. После повышения в чине, осенью 1773 года он получил от Екатерины II письмо, которое его чрезвычайно взволновало. Она писала «Господин генерал-поручик! Вы, я воображаю, так заняты видом Силистрии, что вам некогда читать письма. Я не знаю до сих пор, успешна ли была бомбардировка, но, несмотря на это, я уверена, что — что бы вы лично ни предприняли — не может быть предписано иной цели, как вашему горячему рвению на благо мне лично и дорогой родине, которой вы с любовью служите. Но, с другой стороны, так как я желаю сохранить людей усердных, храбрых, умных и дельных, то прошу вас без необходимости не подвергаться опасности. Прочтя это письмо, вы, может быть, спросите, для чего оно написано; на это могу вам ответить: чтобы вы имели уверенность в том, как я о вас думаю, так же, как желаю вам добра». Прочитав такое игривое и с тонкими намёками письмо, можно было с уверенностью сказать, что оно написано не столько императрицей, сколько женщиной. И Потёмкин, судя по его дальнейшим действиям, понял это.
Желая не упустить свой шанс, Потёмкин, испросив отпуск, отправился в Петербург. Он прибыл туда в январе 1774 года и, чтобы не попасть впросак, еще в течение почти полутора месяцев наводил справки о событиях при дворе, о настроении императрицы в отношении фаворита Васильчикова, а затем, решившись укрепить свои шансы, 27 февраля написал ей письмо с просьбой иметь милость, «если она считает его услуги достойными», назначить его генерал-адъютантом Ея Величества Екатерина благосклонно откликнулась на его письмо через три дня. После удаления Васильчикова Потёмкин занял апартаменты во дворце рядом с апартаментами императрицы. Не только Екатерина, но и многие высокие придворные чины, иностранные послы и «имянитые граждане» России, познакомившись поближе с новым фаворитом, отметили в нём несомненный ум, широкие знания и недюжинные деловые качества.
Сэр Р. Гунинг, английский посол при русском дворе, доносил 4 марта 1774 года: «Васильчиков, способности которого были слишком ограничены для приобретения влияния в делах и доверия государыни, теперь заменен человеком, обладающим всеми задатками, чтобы овладеть тем и другим». А Денис Иванович Фонвизин, относившийся к категории «имянитых граждан», знаменитый автор комедий «Недоросль», «Бригадир» и «Урок дочкам», в письме к сенатору и дипломату Петру Алексеевичу Обрезкову отметил последние новости так: «Здесь у двора примечательно только то, что камергер Васильчиков выслан от дворца, а генерал-поручик Потёмкин пожалован генерал-адъютантом». Звание генерал-адъютанта Ея Величества Императрицы было пожаловано Потёмкину 1 марта 1774 года.
Уже в мае того же года, по распоряжению Екатерины II, Потёмкин был введён в состав Совета, в июне был пожалован графским достоинством Священной Римской империи, в октябре произведён в генерал-аншефы, а в ноябре награждён самым высоким орденом — Св. Андрея Первозванного. Разумеется, так же, как при любых королевских и императорских дворах, у Потёмкина появились завистники, ненавидевшие его. И первым из ненавидящих был наследник Павел Петрович, который жаждал получить трон и понимал, что, пока Потёмкин будет править Россией вместе с императрицей, его мать не уступит ему престола. Но сама императрица была очень довольна своим новым фаворитом и, восхищаясь Григорием Александровичем, говорила: «Ах, что за голова у этого человека! И эта хорошая голова забавна, как дьявол». Эта голова была забавна тем, что она была наполнена идеями государственного значения. Этому фавориту не нужно было устанавливать порядок в придворных кругах. Он был введен в Совет, который позднее приобрёл наименование Государственного, и в скором времени стал в нём главной персоной, а в Военном совете занял председательствующее место. С первых же дней пребывания Потёмкина у престола стало ясно, что этот фаворит в звании генерал-адъютанта способен разделить с императрицей тягость управления огромной страной, да еще с трудно управляемой и требующей реформы государственной структурой.
Екатерина сразу же дала своему новому фавориту серьёзное задание военного характера. В это время на Урале полыхало Пугачёвское восстание, и Потёмкин вместе с генералами Михельсоном и Суворовым должен был принять участие в его подавлении. Первое крупное сражение против восставших пугачёвцев состоялось 22 марта 1774 года. Оно длилось более шести часов и закончилось полной победой правительственных карательных войск, но победа не принесла желаемого результата: волнение продолжалось, и ряды пугачёвского войска пополнялись новыми силами.
Правительственные войска теснили пугачёвцев, но постоянное пополнение пугачёвского войска даже при условии усиления карательных войск не приносило полной победы. По предложению Потёмкина были приняты дополнительные меры по установлению связи с домовитыми старшинами в войске пугачёвцев, а затем в сговоре с ними о выдаче Пугачёва за помилование одних и вознаграждение других. И именно это сработало: 12 сентября 1774 года казаки выдали своего «императора» генералу Михельсону, и Суворов с помогавшим ему Потёмкиным препроводили его в Петербург.
За успешное выполнение этого важного задания Потёмкин получил чин генерал-аншефа (И класс Табели о рангах) и звание шефа иррегулярных войск (то есть не входивших в состав регулярной армии), в основном казачьих, а затем был пожалован в графское достоинство Российской империи.
Когда в российском обществе произносят слово «фаворит», подразумевая, конечно, прежде всего любовника, то обычно это слово связывают с Потёмкиным. А между тем фаворитом-любовником Григорий Александрович Потёмкин был весьма непродолжительное время — всего около полутора лет. Уже в 1775 году фаворитом-любовником Екатерины II стал Пётр Васильевич Завадовский. Но Потёмкин не утратил фавора, он остался помощником императрицы в управлении государством, он получил значение государственного мужа, как пятнадцать лет тому назад мадам Помпадур, фаворитка Людовика XV, перестала быть любовницей короля, но не потеряла титула официальной фаворитки и осталась управлять государством.
По одной из версий, отставка Потёмкина как фаворита-любовника при Высочайшем дворе была связана с тем, что Потёмкин потерял один глаз, окривел. Это произошло случайно: однажды он простудился, и на левом глазу у него возник огромный ячмень. По совету знакомых Потёмкин обратился к лекарю-самоучке Ерофеичу, который изобрёл бальзам — крепкий спиртной напиток, настоянный на травах и употреблявшийся в быту как лекарство при различных кожных воспалениях и нарывах. Ерофеич наложил Потёмкину на глаз повязку, густо смоченную в этом бальзаме. Всю ночь промучился Григорий Григорьевич от боли, но стоически повязку не снял. А утром вместе с ячменём у него вытек и глаз. Потёмкин уже не мог представлять фаворита-любовника с вытекшим глазом, а потому, говорят, сам предложил Екатерине свою отставку. Однако, подобно мадам Помпадур, остался фаворитом как государственный деятель и так же, как она, стал поставлять своей повелительнице новых фаворитов, через которых, помимо переписки с Екатериной, получал информацию, как говорится, «из первоисточника», что еще больше укрепляло его связь с императрицей и позволяло ему оказывать влияние на государственную политику России. По его рекомендации фаворитами Екатерины II стали Зорич, Ермолов, Римский-Корсаков, Ланской, Дмитриев-Мамонов.
При отставке Потёмкина ему «за заслуги государственного значения» Екатерина II пожаловала титул князя Священной Римской империи, земли с крестьянами и всякие драгоценные подарки. В отличие от предыдущего фаворита, который был «отставлен от двора» и не имел права появляться в Петербурге, Потёмкин был при дворе желанным гостем и продолжал оказывать влияние на политику двора Он был нужен императрице как государственный и военный деятель, и уже в следующем, 1776 году она назначила его генерал-губернатором Новороссийской, Астраханской и Азовской губерний. Нужен он был ей и как ближайший, самый верный советник, «хорошая голова», способная предложить необходимые для государства проекты.
По инициативе Потёмкина в 1775 году была ликвидирована Запорожская Сечь, которая вмешивалась в русско-польские дела и угрожала новыми массовыми неповиновениями. По его настоятельному совету и составленному им подробному плану Россия начала дело присоединения Крыма и его хозяйственного освоения.
По отзывам иностранных послов, Потёмкин в России стал самым влиятельным человеком, так что и главы иностранных держав стали через своих послов обращаться к нему по важным вопросам, а король Дании через своего министра просил Потёмкина о содействии сохранению дружбы между Россией и Данией. Екатерина II прекрасно понимала, какое значение для нее и государства имеет деятельность Потёмкина, а потому по её просьбе в 1776 году Иосиф II возвёл Григория Александровича Потёмкина в княжеское Священной Римской империи достоинство с титулом светлости, что признавалось на всей территории Российской империи.