Черное море превращалось временно в основной театр военных действий, но Потемкин придерживался убеждения, что для такой континентальной державы, как Россия, главными остаются военные действия на суше. По этой причине он неутомимо продолжал во время войны реформирование армии на основе своих собственных представлений. Он реорганизовал существующие подразделения, создавал новые части и заботился обо всех вопросах снабжения: вооружении, боеприпасах, снаряжении и продовольствии. Основная забота уделялась личному составу. Потемкин приказал, например, призывать в армию священнослужителей, которые не имели штатной должности, «чтобы они не были бесполезными для общества». Теперь также и провинциальные чиновники, которые праздно проводили время в столице, вынуждены были надеть военную форму. Если местный администратор препятствовал молодежи идти под знамена казаков, он сам должен был вступать в их подразделения. Действия Потемкина имели успех: подразделения казаков, которые состояли в большинстве своем из старообрядцев, превращались в боеспособные и внушающие страх формирования.
Но тем не менее в армии продолжали страдать от волокиты, низкопоклонства и коррупции. Потемкин преодолевал эти негативные явления с более или менее переменным успехом. Еще более трудным было преодолеть недоверие офицерского корпуса. Даже Румянцев высказывался по отношению к Потемкину откровенно: «Я подтверждаю Вам, мой благодетель, что я не так боюсь изменений или новшеств, а того, что у меня не будет достаточно сноровки для этого и я не сумею достичь успехов». Старый офицерский корпус не доверял возмутителю спокойствия, и он не скрывал своего презрения к его действиям. Война свела их вместе, хотели они того или нет, и от всех требовалась кропотливая повседневная работа, в том числе и от Потемкина.
В этом отношении участь Екатеринославского корпуса служит наглядным примером разнообразных беспорядков. Корпус был создан весной 1787 года. Прекрасное подразделение предназначалось для подготовки к войне с Турцией и для большой поездки Екатерины на юг страны. Для формирования корпуса выбирали армейского офицера, которому при успешном исполнении служебных обязанностей присваивалось звание генерал-майора. Потемкин спрашивал кандидата о том, готов ли тот отличиться с заданием. Он отвечал согласием и приступал решительно и бодро к работе. Однако до начала войны в августе 1787 года он выполнял обязанности не должным образом, и Потемкин в ноябре передал командование корпусом Суворову. Потемкин инспектировал солдат в Херсоне и пришел к удручающему выводу: «В Херсоне неразбериха, и полки в плачевном состоянии. Я прибыл, чтобы провести инспектирование и ревизию. Екатеринославский полк используется не по назначению. Полно молодых людей, которых нужно тренировать».
До марта 1788 года корпус под командованием Суворова набирал силу. Но в нем был очень высокий процент больных солдат. Очевидно, проблемы не могли быть решены, и корпус постигла участь неукомплектованных подразделений: он был расформирован, а солдаты должны были восполнить потери в других частях. При этом необученные новобранцы могли быть посланы в сухопутные войска и на флот. В мае 1789 года корпус снова был восстановлен. Новые рекруты получили предварительную подготовку на Буге, чтобы интегрироваться в регулярные войсковые соединения.
В регулярной армии, а также в казачьих территориальных формированиях имелось много подразделений, которых постигла похожая участь: в силу сложных объективных и субъективных предпосылок их формировали, обучали, посылали в бой, расформировывали и снова формировали. Постоянные изменения структуры принадлежали, очевидно, к стилю ведения войны. При этом никакая мелочь не ускользала от глаза Потемкина. Он заботился обо всем и решал основные задачи по охране колонизированной страны и по ведению войны с Турцией. Сколько проблем было только в бесперебойном снабжении подразделений продуктами питания! Проблема заботы о благе и образовании солдат в интересах основной цели была очень нелегким делом для генерала-губернатора и главнокомандующего. Эта забота забирала много сил и нервов и наталкивалась на сопротивление.
В письме от 14 августа 1787 года канцлеру Безбородко в связи с началом войны и большим количеством больных в Херсоне Потемкин писал: «Это лишает спокойствия меня, но, слава Богу, немногие умирают». Между тем Суворову был дан приказ: «Вы должны строго приказать своим командирам, чтобы новобранцы не подвергались телесным наказаниям, обучать их служебному долгу следует обучением и порядком». Потемкин издавал строгие указания для обеспечения гигиены. Он содействовал учреждению госпиталей и военных лазаретов и построил целую сеть таких учреждений в важных городах. Тем не менее многое оставалось только в зародышевом состоянии.