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