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