Энергия и честолюбие толкали его к перемене места и судьбы в целом. Недолго думая о выборе дальнейшего рода деятельности, Григорий Александрович решил определиться на военную службу. Отправившись в Петербург, он поступил в Конную гвардию, вскоре стал вахмистром. В числе гвардейцев, участвовавших в перевороте 1762 г., сделавшем императрицей Екатерину И, был ею замечен и награжден. Она пожаловала его в подпоручики гвардии и подарила 400 душ крепостных. Пытаясь пробить себе путь в жизни, он долгое время безуспешно пытался сблизиться с братьями Орловыми, составлявшими тогда опору Екатерины, занимал различные незначительные должности при дворе.
Не добившись приближения к императрице, молодой честолюбивый офицер в 1769 г. отправился на русско-турецкую войну, сражался в рядах 1-й армии генерал-аншефа А. Голицына, отличился при разгроме войск Молдаванчи-паши и занятии Хотина, за что был удостоен чина генерал-майора.
Сменивший Голицына на посту командующего П. Румянцев увидел в Потемкине перспективного и расторопного человека. Он дал ему возможность проявить себя в военных походах. Молодой генерал доблестно действовал при Фокшанах, участвовал в знаменитых сражениях при Ларге и Кагуле. Он первым ворвался в предместья Килии, отличился храбростью в схватках с противником под Крайовом и Цимбрами, участвовал в разгроме войск Осман-паши под Силистрией. Наградами ему за доблесть в боях стали чин генерал-поручика, ордена Святой Анны и Святого Георгия III степени.
Своими подвигами и письмами к Екатерине Потемкин обратил на себя ее внимание. Императрица в переписке с ним настаивала на том, чтобы он напрасно не рисковал жизнью, и через месяц после получения этого письма Потемкин уже был в Санкт-Петербурге, где стал генерал-адъютантом, подполковником Преображенского полка, членом государственного совета и, по отзывам иностранных послов, стал «самым влиятельным лицом в России».
Получая во всем поддержку государыни, Григорий Александрович фактически стал ее соправителем, ближайшим помощником во всех государственных делах. Он сразу же принял на себя заботы по подавлению восстания Е. Пугачева, организовав военные действия против повстанцев. Не засиживаясь подолгу в столице, Потемкин приступил к плану хозяйственного освоения и военного укрепления юга России. За короткий срок он был произведен в генерал-аншефы и назначен вице-президентом Военной коллегии, стал членом Государственного совета, графом, был удостоен орденов Святого Андрея Первозванного и Святого Георгия II степени, пожалован княжеским достоинством Священной Римской империи.
В 1775 г. Потемкин решительными действиями ликвидировал Запорожскую Сечь и положил начало запорожскому казачьему войску, полностью подвластному российской короне. В 1776 г. он становится генерал-губернатором Новороссийской, Азовской и Астраханской губерний. Правитель юга обдумывал план борьбы с Турцией вплоть до уничтожения турецкого государства и воссоздания Византии. При устье Днепра Потемкин заложил Херсон с корабельной верфью, руководил строительством Екатеринослава (ныне Днепропетровск), освоением Кубани, действиями русских войск на Кавказе. В его руках было сосредоточено управление всей южной Россией от Черного до Каспийского моря.
Из огромного числа деловых бумаг и писем канцелярии Потемкина видно, насколько разнопланова и непрерывна была его деятельность по управлению Южной Россией. Хотя во всех начинаниях чувствуется лихорадочная поспешность, самообольщение, хвастовство и стремление к чрезмерно трудным целям. Как будто намеренно он завышал себе планку и пытался переступить через человеческие возможности. Приглашение колонистов, закладка городов, разведение лесов и виноградников, поощрение шелководства, учреждение школ, фабрик, типографий, корабельных верфей — все это предпринималось чрезвычайно размашисто, в больших размерах, не щадя ни денег, ни труда, ни людей. Многое было начато и брошено — другое с самого начала оставалось на бумаге. Осуществилась лишь самая ничтожная часть смелых проектов Григория Александровича Потемкина. Но и она впечатляла!
8 апреля 1783 г. императрица подписала манифест, окончательно закрепляющий Крым за Россией. Первыми шагами Потемкина по реализации этого манифеста стали строительство Севастополя как военного и морского порта России и создание Черноморского флота, как военного, так и торгового.