Положите же теперь, что Крым Ваш и что нет уже сей бородавки на носу, — вот вдруг положение границ прекрасное…» 14 декабря 1782 г. императрица подписала рескрипт о необходимости при первом же поводе присоединить Крым к России. Осуществление этого плана завершилось ликвидацией Крымского ханства. Одновременно манифест от 8 апреля 1783 г. извещал о включении в число владений Российской империи Тамани и Кубани.
Несмотря на появление у Екатерины II новых фаворитов, положение Потемкина все более укреплялось. В феврале 1784 г. он стал президентом Военной коллегии, получил чин генерал-фельдмаршала и был назначен шефом Кавалергардского полка. В следующем году ему подчинили Черноморское адмиралтейство и флот, а еще через год он организовывал Кавказское и Сибирское войска.
В 1787 г. Екатерина II предприняла путешествие на юг, организованное Потемкиным, который сумел показать все успехи в деле освоения новых земель. «Путешествие императрицы, — писал участник ее поездки, — можно назвать волшебством. На каждом почти шагу встречали мы нечаянное, неожиданное. Там видели эскадры, там конные отряды, там освещение, на несколько верст простиравшееся; здесь сады в одну ночь сотворенные». Царица велела Сенату подготовить похвальную грамоту с перечислением подвигов генерал-фельдмаршала князя Потемкина: в присоединении Тавриды к Российской империи, в успешном заведении хозяйствования Екатеринославской губернии, в построении городов и Черноморского флота, с прибавлением ему почетной приставки Таврический.
Огромны заслуги светлейшего князя и в реорганизации русской армии: в 1786 г. им был издан новый устав, полностью заменена была военная форма. Фельдмаршал писал: «Я употребил всю свою возможность к избежанию излишеств и, облегча человека, дал однако же все, что может служить к сохранению здоровья и к защите от непогоды…»
Влияние Потемкина на армию поистине было благотворным. Все его мероприятия направлены прежде всего на облегчение условий службы солдат. Вместо неопределенного пожизненного срока службы — «доколе силы и здоровье позволят» — был введен 25-летний срок; в кавалерии полагалось служить 15 лет, после чего переводиться в пехоту либо в гарнизоны. Солдат стали в первую очередь обучать тому, что могло пригодиться в бою или походе. Телесные наказания, и гак редко применявшиеся Румянцевым, были при Потемкине совершенно выведены из обихода армии. С другой стороны, фельдмаршал был сторонником строгой дисциплины: «Я предписал, чтобы наказания были легкие, но если бы кто дерзнул перед командиром быть ослушным, того я накажу равным смертным наказанием».
При светлейшем князе вновь были сформированы отдельные егерские батальоны, создан новый тип регулярной конной кавалерии — легкоконные полки, образовано четыре конно-егерских полка, в два раза увеличено число драгунских полков; полностью переформирована артиллерия, в рядах которой была образована конная артиллерия. Деятельность Потемкина особенно сказалась в устройстве казачьих войск. Формировались Терское, Моздокское и Кубанское казачьи войска на Кавказе, а в верховьях Дона — Хоперское казачье войско. На случай военных действий казачьи войска могли выставить до 50 полков. Всего же к концу царствования Екатерины II общая численность всех действующих войск увеличилась до 287 тысяч человек. В 1788 г. при участии Потемкина были составлены «Примечания о причинах болезней» с требованиями заботиться о санитарном состоянии войск. При нем всегда высокая смертность в армии начала снижаться, хотя и оставалась достаточно большой. Внес он свой вклад, наряду с Румянцевым и Суворовым, и в развитие служебных уставов — строевых, полевых и гарнизонных, развитие способов ведения боя. По предпринятым Потемкиным военным реформам его можно поставить в один ряд с такими великим военными реформаторами, как Петр I и Румянцев, а позднее Суворов, хотя он и уступал им в полководческих дарованиях.
13 августа 1787 г., всего через несколько дней после возвращения Екатерины II из Крыма, Турция объявила войну России. Турецкий султан Селим III, опираясь на поддержку Пруссии, Швеции, Англии и Франции, требовал возвращения Крыма и признания Грузии своим вассалом. Стремясь использовать выгоду положения нападающей стороны, турки сразу же проявили большую активность на море и 1 октября высадили десант на Киибурнской косе, который был уничтожен войсками А. В. Суворова. Турки потеряли до 5 тысяч человек, а турецкий флот вынужден был уйти в море.