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