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