Столичный губернатор возложил на Кутузова ведение дел собственной канцелярии. «Маловразумительные» обязанности оказались непростыми. Инженер-прапорщик исполнял их не только добросовестно, «обнаружив свои способности к делам гражданским, но еще более старался употребить все меры к приобретению навыка в них и опытности». Думается, все же эта адъютантская служба была не в характере молодого офицера, высокообразованного, с командирскими задатками, стремившегося к армейской службе.
Принц Голштейн-Бек остался доволен своим флигель-адъютантом. Когда через полгода штаб генерал-губернатора расформировали, он предложил Военной коллегии распределить М. Голенищева-Кутузова капитаном для определения в полк «здешней команды», то есть расквартированный недалеко от Санкт-Петербурга.
21 августа 1762 года Михайла Голенищев-Кутузов, еще не достигший 15-летия, производится в капитаны и назначается командиром роты в Астраханский пехотный полк. (Через десять дней, 31 августа, в командование этим полком вступает 32-летний A.B. Суворов, которому суждено будет стать военным гением России.)
С пребывания в Астраханском пехотном полку, одном из лучших по своей выучке в частях русской армии, началась более чем полувековая служба М.И. Голенищева-Кутузова в российских войсках.
Астраханский полк вел свою родословную с 1700 года (был создан по велению Петра I) и являлся одним из старейших в русской регулярной армии. Организационно астраханцы входили в состав Санкт-Петербургской дивизии, которой официально командовала «по своей природе» сама матушка-императрица Екатерина II.
Полк размещался в небольшом городке Новая Ладога, вблизи столицы, занимаясь боевой подготовкой в месте своего расквартирования, но для несения караульной службы, в том числе и дворцовой, регулярно вызывался на несколько месяцев в Санкт-Петербург.
Служба 15-летнего ротного командира в армейском полку под командованием полковника A.B. Суворова стала прекрасной школой для будущего главнокомандующего русской армией в Отечественной войне 1812 года. Суворов принял полк после возвращения с Семилетней войны, где зарекомендовал себя бесстрашным боевым офицером, послужившим на различных штабных, строевых и интендантских должностях. Он был верен себе: накопленный опыт участника большой войны в Европе стал достоянием подчиненных — офицеров, унтер-офицеров и нижних чинов Астраханского пехотного полка.
Сторонник быстрого маневренного боя, свои взгляды на ведение боевых действий Суворов воплощал в повседневную учебу и воспитание астраханцев. Уже в скором времени, на учениях, его полк поражал всех высокой выучкой личного состава и инициативностью полкового командира в ходе маневров. То, что Кутузов в офицерской молодости прошел суворовскую полковую школу, в будущем послужит ему самым добрым образом.
Едва ли не самым главным стало то, что Кутузов за время своего пребывания в Новой Ладоге сполна познал суворовскую «Науку побеждать». Бессмысленная строевая муштра и изучение простейших приемов в строю заменялись обучением солдат тому, что в первую очередь от них потребуется на войне: штыковым атакам, прицельной стрельбе из ружей, залповому огню, форсированию водных преград, марш-броскам — не по «битым путям», а по целине, по лесам и болотам. Астраханский пехотный полк многократно поднимался по тревоге и в любую погоду уходил без обозов на полевые учения. Пехотинцев учили вести ночные атаки, быть смелыми, устремленными на достижение победы. Суворовское правило гласило: «Тяжело в учении — легко в бою».
Очевидцев больше всего поражали учебные сквозные штыковые атаки, когда два батальона полка шли в штыки друг против друга. При ударе в штыки Суворов приказывал наступающим ни на секунду не задерживаться, но, как бы ни был силен удар, он не позволял отражающим его отойти и только в последнее мгновение разрешал поднять вверх штыки, чтобы солдаты не поранили друг друга в начинающейся отчаянной схватке.
На роты пехоты «в полный карьер на саблях» скакала кавалерия, и опять, чтобы научить пехотинцев выдерживать этот натиск, только в самое последнее мгновение солдатам разрешалось разомкнуться и пропустить сквозь свои ряды кавалеристов. Учились не только люди, но и кони. Позади строя пехоты Суворов приказал ставить лукошки с овсом, и лошади привыкали прорываться сквозь строй людей, зная, что за ним их ждет «поощрение».
Капитан Кутузов лично участвовал в таких суворовских учениях, проходя прекрасную школу младшего армейского командира. Его рота числилась в числе лучших, в ней всегда проявлялась, даже в мелочах, забота о нижних чинах. Здесь не было, как и во всем Астраханском полку, рукоприкладства, унижения человеческого достоинства.
Полковой командир успел хорошо изучить способности капитана М.И. Кутузова и оценить их. В суворовской характеристике подчиненному, данной в феврале 1763 года и утвержденной петербургским обер-комендантом генерал-поручиком И.И. Костюриным, говорилось:
«В должности звания своего прилежен и от службы не отбывает, подкомандных своих содержит, воинские экзерцицы обучает порядочно и к сему тщение имеет, лености ради больным не репертовался и во всем ведет себя так, как честному обер-офицеру подлежит, и как по чину своему опрятен, так и никаких от него непорядков не происходит, и таких пороков, коим в указе гос. коллегии 1756 году генваря 20 дня написаны, не имеет, чего ради по усердной его службе к повышению чина быть достоин».
Совместная служба с Суворовым продолжалась всего семь быстро пролетевших месяцев. Высочайшим указом полковник A.B. Суворов назначается командиром Суздальского пехотного полка. Первой суворовской наукой для молодого ротного командира стало твердое убеждение, что главная сила русской армии в ее солдате, что, только завоевав его доверие и любовь, можно требовать от него полной отдачи в бою, мужественного перенесения всех тягот и лишений в ратной службе. Это убеждение Кутузов пронесет через всю жизнь.
В начале военной карьеры Михаиле Голенищеву-Кутузову везло с наставниками и учителями. Доверительные отношения сложились у него в начале 60-х годов со своим двоюродным дядей Иваном Логиновичем Голенищевым-Кутузовым, флотским офицером, ставшим генерал-интендантом флота, членом Адмиралтейств-коллегии в чине генерал-майора. Перед этим он был начальником Морского кадетского корпуса, более столетия бывшего главным поставщиком офицерских кадров в военные флоты России.
Дядя стал для племянника добрым советчиком, умным наставником и старшим товарищем, Кутузов питал к нему чисто сыновьи чувства и часто, уже в зрелом возрасте, называл его в письмах своим «батюшкой». От дяди молодой офицер вобрал в себя очень многое: любовь к русской литературе, стремление к изучению иностранных языков и главное — интерес к государственным делам.