Представленный принцем императрице Екатерине II в бытность ее в 1764 г. в Ревеле, Голенищев-Кутузов просил ее назначить его волонтером в войска, направленные в Польшу для борьбы с конфедератами. Просьба его была уважена, и Голенищев-Кутузов был отправлен в распоряжение генерала И. И. Веймарна, который назначил его для руководства действиями мелких отрядов, ведших партизанскую войну без достаточной связи между собою.
Хотя Голенищев-Кутузов и говорил впоследствии об этом периоде своей жизни, что он тогда «войны еще не понимал», но все же зарекомендовал себя за это время отличным офицером и в 1770 г., с начала 1-й турецкой войны, был назначен в армию Румянцева, в отдельный корпус генерала Бауэра для «доверенных поручений». Когда же Бауэр был назначен главным квартирмейстером армии, Голенищев-Кутузов, пользовавшийся полным его доверием, был сделан обер-квартирмейстером. За отличие в боях при Рябой Могиле, Ларге и Кагуле Голенищев-Кутузов был произведен из капитанов прямо в премьер-майоры, в декабре 1771 г. – в полковники.
Неосторожная шутка Голенищева-Кутузова в товарищеском кругу по адресу Румянцева была причиной внезапного перевода его из Дунайской армии в Крымскую и вместе с тем резкой перемены в его характере. До тех пор живой и общительный, Голенищев-Кутузов стал сдерживать порывы своего остроумия и пылкого ума, скрывать свои чувства под маской любезности со всеми, стал очень недоверчив, осторожен и хитер.
По прибытии в Крымскую армию Голенищев-Кутузов был назначен в отряд генерала Кохиуса, направленный в июле 1774 г. к укрепленной крымцами деревне Шумы, близ Алушты. Со знаменем в руке, впереди своих солдат, Голенищев-Кутузов ворвался в Шумы, выбил из нее татар и, энергично преследуя их, был тяжело ранен в левый висок пулей, вышедшей у правого глаза.
Отправленный для излечения в Санкт-Петербург, он был представлен императрице, которая пожаловала ему орден Св. Георгия IV степени и отправила для лечения за границу, щедро снабдив деньгами. Голенищев-Кутузов воспользовался пребыванием за границей, чтобы изучить постановку военного дела в Пруссии и Австрии.
По возвращении в Россию в 1776 г. Голенищев-Кутузов, по избранию самой императрицы, был послан в Крым в помощь Суворову при водворении в крае спокойствия и утверждении русской власти. Здесь началось сближение этих двух великих полководцев, и, покидая Крым, Суворов рекомендовал Голенищева-Кутузова в помощники преемнику своему – де Бальмену.
В 1782 г. Голенищев-Кутузов был произведен в бригадиры; в 1784 г. он склонил Крым-Гирея, последнего крымского хана, отречься от престола и уступить России свои владения от Буга до Кубани. За это Голенищев-Кутузов был произведен в генерал-майоры и назначен шефом Бугского егерского корпуса. В 1786 г, на маневрах Голенищев-Кутузов еще раз получил выражение особого к себе внимания императрицы. Увидав его скачущим на чрезвычайно горячем коне, Екатерина II сказала ему: «Вы должны беречь себя. Запрещаю вам ездить на бешеных лошадях и никогда не прощу, если услышу, что вы не исполняете моего приказания».