За границей с 1776 г. Кутузов становится членом масонской ложи в Регенсбурге. Считается, что позднее его кооптируют в масоны Франкфурта, Вены, Берлина, Санкт-Петербурга и Москвы. В 1777 г. вернувшийся на родину «привечаемый» императрицей подполковник Тульского пехотного полка получил… чин полковника (10.06.1777 г.) и командование Луганским пикинерским и Мариупольским легкоконным полками. Будучи отменным кавалеристом, он быстро привел порученных ему пикинеров в превосходное состояние. Занимаясь наведением порядка (сегодня это называется «зачисткой» от бандформирований) в Крыму под началом генерал-поручика А. В. Суворова, Кутузов, несмотря на то что они были людьми с совершенно противоположными характерами, сумел-таки сработаться с очень противоречивым Александром Васильевичем. За непростую работу по присоединению Крыма к России – «участвовал самым деятельнейшим образом во всех распоряжениях и мерах, которые приняты были к усмирению мятежников и к восстановлению тишины и спокойствия» – в 1782 г. Михаил Илларионович становится бригадиром, а в 1784 г. – уже генерал-майором. Кроме того, он успел пройти все должности от командира полка до командующего корпусом, а это уже был полководческий формат! Генеральский чин он получил за успешные переговоры с Гиреем, последним крымским ханом, которого он сумел убедить в целесообразности отречения от престола и признания права России на земли от Буга до Кубани. Правда, в том же году его постигло большое личное горе: в своем имении – селе Тупино Торопецкого уезда Псковской губернии скончался его отец, который совсем недавно оставил пост сенатора «за приключившейся болезнью». Получив отпуск по семейным обстоятельствам, Михаил Илларионович решает вопросы наследования – закрепления за ним и братом поместий, имевшихся в трех уездах. После долгой канцелярской волокиты и исконно российского бюрократизма раздел наследства прошел небыстро, и в конце концов Михаил Илларионович смог унаследовать имения в Псковском и Екатеринославском наместничествах, «мужска полу 450 душ». Остальное отошло брату Семену и сестре Дарье.