Екатерина начала использовать административный талант Потемкина с 1763 года, когда узнала о его интересе к религии, и назначила ассистентом прокурора Священного Синода, который управлял делами и финансами церкви. В то же время она способствовала и его повышению по военной службе, и к 1767 году он стал старшим командиром конной гвардии. На следующий год Потемкин был назначен придворным камергером. Когда собрали Уложенную комиссию, Потемкину отвели роль куратора представителей от татар и других этнических меньшинств Российской империи. Впоследствии Потемкин испытывал особый интерес к субъектам Российской империи, населенным другими этносами; он обладал высшей властью на юге, и его окружали лидеры народов, исповедовавшие разную религию. Однако он не утратил свою прежнюю любовь к церковной полемике. Потемкин не упускал возможность обсудить вопросы веры с представителями других религий. Когда началась первая русско-турецкая война в 1769 году, он добровольцем отправился на фронт. С позволения Екатерины Потемкин присоединился к армии генерала Румянцева, в которой служил сначала в качестве адъютанта, а затем – командира кавалерии и добился больших успехов на поле боя. В признание за службу он был возведен в чин генерал-майора, и в ноябре 1769 года ему было поручено передать Екатерине отчеты Румянцева о ведении боевых действий. В Санкт-Петербурге Потемкина приняли как заслуженного командира и пригласили на обед к императрице.
Когда он вернулся в армию на юге, то получил от Екатерины позволение писать ей лично. Она была удивлена, что Потемкин не спешил воспользоваться своей привилегией. 4 декабря 1773 года она решила приободрить его:
Вероятно, Потемкин смог прочитать скрытое приглашение, содержавшееся в этом письме. В январе 1774 года, когда его армия была расквартирована на зиму, он покинул ее и поспешил в Санкт-Петербург.
По прибытии он узнал, что правительство во главе с Екатериной пыталось разрешить ряд критических моментов. Война с Турцией длилась уже шесть лет, бунт Пугачева был в самом разгаре, а близкие отношения Екатерины с Васильчиковым переживали свою последнюю стадию. Потемкин считал, что его вызвали по личным причинам, и был раздражен, увидев, что Васильчиков ни на шаг не отходил от императрицы. Он просил о личной аудиенции у Екатерины, и 4 февраля отправился в Царское Село. Она сказала, что хотела бы держать его подле себя. Потемкин вернулся ко двору и, казалось, был счастлив, продолжая развлекать Екатерину. Все признавали в нем наиболее вероятную кандидатуру на роль нового фаворита. Есть версия, что однажды он поднимался по лестнице дворца и встретил спускавшегося вниз Григория Орлова. «Какие новости при дворе?» – спросил Потемкин. «Ничего особенного, – ответил Орлов. – За исключением того, что вы поднимаетесь наверх, а я – спускаюсь вниз». Васильчиков смог удержаться на своем месте еще несколько недель, поскольку Екатерина не была уверена в том, какое впечатление подобные перемены могут произвести на общество в Санкт-Петербурге и зарубежные державы, к тому же она боялась настроить против себя Панина, отвергнув его протеже. Но более всего она хотела убедиться, что не ошиблась с новым избранником.