В круг приближенных императрицы Потемкин вошел после целого ряда побед, одержанных во время русско-турецкой войны 1768–1774 годов (наиболее яркие из них – под Фокшанами, Ларгой, Кагулом). За успешные военные действия против турок он был награжден орденами Св. Анны и Св. Георгия. Его начальник, генерал Румянцев, в письме к императрице отзывался о Потемкине как о мужественном и храбром воине, который сражается не щадя себя. В одном из писем, датированном 1773 годом, императрица дала понять, что и впредь собирается поддерживать отношения с Потемкиным. В 1774 году он был отозван в Петербург, назначен генерал-адъютантом, вице-президентом Военной коллегии и возведен в графское достоинство. Считается, что именно с этого момента роман Потемкина и Екатерины II становится чем-то большим, нежели отношения фаворита с венценосной особой. Существует версия, что их союз был скреплен брачными узами (разумеется, венчание происходило тайно). А в 1775 году у них родилась дочь Елизавета, которая воспитывалась в семье А. Н. Самойлова – племянника Потемкина (в метриках она значилась под именем Елизаветы Григорьевны Темкиной).
Роман Екатерины II и Потемкина был исключительно ярким. Императрица осыпала фаворита милостями, награды ее были воистину «царскими»: звания, ордена, деньги и драгоценности сыпались золотым дождем. По свидетельствам современников, за десять лет (с 1774 по 1784 г.) им было получено наличными деньгами и драгоценными вещами 18 миллионов рублей. Он имел право обращаться в Казенные палаты со своими требованиями. Практически все европейские государства представили Потемкина к высоким наградам – политики очень быстро сумели разобраться, что новый избранник Екатерины имеет на нее огромное влияние, выходящее далеко за пределы опочивальни. Пруссия наградила его «Черным орлом», Польша – «Белым орлом» и «Святым Станиславом», Швеция – «Святым Серафимом», Дания – «Белым слоном». А в марте 1776 года Потемкин получил титул князя Священной Римской империи (именно с тех пор его стали называть «светлейшим» – от титулования «ваша светлость»).
В свою очередь, Потемкин изо всех сил старался быть полезным российской короне и той, которая эту корону носила. Он усмиряет восстание Пугачева, решает весьма важную на тот момент проблему Запорожской Сечи, ликвидировав вольницу и превратив Сечь в организованное войско, подвластное императрице. В 1776 году он становится генерал-губернатором Новороссийской, Азовской и Астраханской губерний. Получив это назначение, Потемкин занялся хозяйственным освоением и военным укреплением южно-русских земель. Он основал при устье Днепра город Херсон с корабельной верфью, руководил строительством Екатеринослава (современный Днепропетровск), занимался освоением Кубани. Результаты этой деятельности были высоко оценены потомками: некоторые из них полагали, что Потемкин сделал для юга России не меньше, чем Петр Великий – для севера.
Проекты светлейшего отличались смелостью и грандиозным размахом. Он одним из первых понял значение Крыма для России и писал Екатерине о необходимости его присоединения: «Крым положением своим разрывает наши границы… Положите же теперь, что Крым Ваш и что нет уже сей бородавки на носу – вот вдруг положение границ прекрасное…» Как только манифестом от 8 апреля 1782 года Крым был закреплен за Россией, Потемкин принялся осваивать новые земли. Он заложил военный и морской порт Севастополь, основав базу для создания Черноморского флота. Его отсутствие в столице создало благоприятную почву для появления новых фаворитов. Однако ни один из них не смог подняться в глазах Екатерины настолько высоко, чтобы Потемкин впал в немилость. Более того, некоторые исторические документы позволяют предположить, что Екатерина советовалась с князем относительно своих любовников и действовала с его полного согласия. Впрочем, он также не был верен императрице: сохранились любовные записки Потемкина к целой плеяде красавиц, а в воспоминаниях современников он и вовсе выглядит донжуаном. В этом нет ничего удивительного: при дворе (и не только российском) прекрасно умели разграничивать любовь и «вдохновение плоти».
В 1784 году Екатерина произвела Потемкина в звание генерал-фельдмаршала, назначила президентом Военной коллегии и генерал-губернатором Крыма, называвшегося в те времена Таврической областью. А через три года императрица со свитой и приглашенными представителями европейских царствующих семей (среди которых был австрийский император Иосиф II) отправилась в инспекционную поездку на юг России.