По Георгиевскому трактату, подписанному в 1783 году с царем Ираклием, российская граница передвинулась с севера Кавказа в Тифлис. К этому времени владения и проекты Потемкина стали уже так обширны, что он советовал императрице создать отдельное Кавказское наместничество, которое состояло бы из Кавказской, Астраханской и Саратовской губерний, — разумеется, под его управлением. Наместником был назначен энергичный кузен князя Павел Потемкин: построив Военно-Грузинскую дорогу через горы в Тифлис, он стал населять новые города государственными и монастырскими крестьянами. Только в 1786 году в распоряжение светлейшего поступили 30 307 человек из внутренних губерний для заселения Кавказа (и Екатеринослава). Павел Сергеевич, подобно своему могущественному родственнику, превратил Екатериноград в подлинную столицу наместничества и завел там двор в роскошном дворце.

В 1785 году на Кавказе появился вождь в зеленом плаще, называвший себя Шейхом Мансуром (Победителем). Он проповедовал идеалы суфийского братства Нашбанди и объявил газават — священную войну против русских. Никто никогда не узнает, кем он был на самом деле: возможно, пастухом-чеченцем по имени Ушурма, родившимся в 174$ году. Однако, согласно одной из версий, он был сыном итальянского нотариуса из Монтеферрата, его настоящее имя было Джо-ванНо Баттиста Боэтти, он сбежал из дома, стал доминиканским миссионером, принял ислам, изучал коран в бухарском медресе и сделался воином. Со своими горцами, предшественниками шамилевских мюридов, Мансур сумел истребить колонну русских войск из 600 человек. Впрочем, он чаще проигрывал, чем побеждал, и все же продолжал возглавлять коалицию горцев, и имя его стало легендой.

Войной против Шейха Мансура руководил из Екатеринограда Павел Потемкин. Но архивы светлейшего показывают, что верховное командование кавказскими и кубанскими корпусами принадлежало ему. В 1787 году, перед тем, как разразилась вторая война с Турцией, побежденный Мансур бежал на турецкую территорию. Когда началась война, он был готов сражаться снова. Русским так и не удалось полностью подавить горское сопротивление, и так называемые войны с мюридами продолжались почти весь следующий век. Не прекратились они и до сих пор.

Князь строил на юге дворцы, достойные наместника, если не царя. У него был большой дом в Кременчуге, а обширный дворец в Херсоне, с двумя двухэтажными флигелями и центральным четырехэтажным корпусом, был главным зданием нового Города. Славу потемкинских «Афин» составлял монументальный Екатеринославский дворец, построенный по проекту Ивана Старова, с двумя крыльями, простирающимися на 120 метров от портика с шестью колоннами. Садовник Потемкина Уильям Гульд приехал на юг вслед за Старовым с сотнями рабочих. В Екатеринославе он разбил английский парк и создал возле дворца две оранжереи, подчеркивая сочетание «изящества и практичности», как сам он писал князю.

Удивительно, но в Крыму Потемкин не построил для себя ни одного крупного дворца, хотя в Карасубазаре Старов возвел для него особняк из розового мрамора. Последний его дворец, в Николаеве, высится на утесе у слияния двух рек. Он декорирован местными архитекторами в молдавско-турецком стиле и имеет купол с четырьмя башнями, напоминающими минареты.