«Хлопот здесь множество, – писал Михаил Илларионович жене из Константинополя, – нету в свете министерского посту такого хлопотливого, как здесь, особливо в нынешних обстоятельствах, только не все так мудрено, как я думал… Дипломатическая кариера сколь ни плутовата, ей-богу, не так мудрена, как военная, ежели ее делать как надобно…» Кутузову удалось значительно улучшить отношения между Турцией и Россией. Свои власти он убедил в том, что Порта не готова начинать новую войну и тем самым сорвал провокацию, готовившуюся западными дипломатами. Он добился права для русских судов плавать в районе Архипелага и заходить в турецкие порты, было достигнуто ограничение влияния западных стран на турецкую внешнюю политику.
По возвращении из Турции Кутузов был назначен директором Сухопутного кадетского корпуса. Тогда это было основное военно-учебное заведение, готовившее офицеров для русской армии. Кутузов решительно изменил весь учебный процесс. Основное внимание с его появлением стали уделять преподаванию специальных военных дисциплин: тактики, военной истории. Стали проводиться регулярные занятия на полигонах и в лагерях.
Дополнительно на Михаила Илларионовича возложили обязанности командовать сухопутными войсками в Финляндии. Проведя тщательную ревизию и добившись дотаций от государства, Кутузов принялся энергично укреплять границу со Швецией. Летом 1796 года он занимался подготовкой и отправкой 1-го и 2-го морских полков на Рончесальмскую эскадру для совместных с ней учений, ведал отправкой пополнений в Сайменскую флотилию. Привлекался Кутузов и к участию в общеармейских маневрах в районе Гатчины в сентябре 1797 года.
В отличие от Суворова, Михаил Кутузов спокойно ужился с Павлом I, хотя и не поддерживал прусских нововведений в армии. Но этот генерал уже давно предпочитал не вступать в конфликт с властями. Павел, как и его мать, очень ценил Михаила Илларионовича, называл «мой Кутузов». В конце декабря 1797 года Кутузов получил указание отправиться в Берлин с дипломатическим поручением. Здесь ему надлежало исполнить задачи, не менее сложные, чем в свое время в Константинополе: предстояло подготовить почву для переговоров относительно привлечения Пруссии на сторону России в борьбе с Францией. В прусской столице Кутузова встретили с огромным уважением. Хотя он и должен был, по идее, лишь помогать находившемуся здесь Панину, отношение королевской семьи к прославленному генералу было необычайно теплым. Буквально со дня своего приезда он уже ужинал с королевской семьей. Король Фридрих Вильгельм III говорил, что Павел не мог дать лучшего доказательства своей дружбы, чем избрав своим представителем Михаила Илларионовича. Кутузов пробыл в Берлине два месяца. Он сумел не допустить сговора Пруссии с Францией, и наоборот, создать условия для вовлечения Пруссии в антифранцузскую коалицию.
Завершив миссию, Михаил Кутузов отправился в Выборг к месту своей новой службы по должности инспектора Финляндской инспекции. По указанию императора он вел переговоры со шведской стороной о демаркации границы, вновь проявив большое дипломатическое искусство. В октябре 1799 года Кутузов получил назначение командовать экспедиционным корпусом в Голландии, где он должен был действовать совместно с англичанами против французов. Кутузов успел доехать лишь до Гамбурга, когда англичане эвакуировали свои войска с континента, и русский генерал был отозван домой. 6 ноября он был назначен Литовским военным губернатором и инспектором инфантерии (пехоты) Литовской и Смоленской инспекций. Было решено укреплять западные границы государства. Войска должны были располагаться двумя линиями. Первая предназначалась для командования Суворову, одной из трех армий второй линии должен был командовать Михаил Кутузов. Все это делалось в связи с перспективой борьбы против Франции. Летом 1800 года план был переработан. Теперь предполагалось сформировать на западной границе Российской империи две армии: одну под командованием Палена, а другую – генерала от инфантерии Кутузова. В преддверии большой пограничной работы в Гатчине осенью опять прошли широкомасштабные маневры, в которых Кутузов, естественно, играл одну из ведущих ролей.
В своем округе Михаилу Илларионовичу приходилось много заниматься вопросами укомплектования частей и соединений рекрутами, снабжением войск оружием, боеприпасами, амуницией и продовольствием. В войсках Кутузова наблюдался образцовый порядок. Одновременно отвечал он и за политическое состояние в Литовском крае. По самому последнему павловскому плану действий против Франции Кутузов был уже главным кандидатом на пост главнокомандующего всеми вооруженными силами. В его ведение в ноябре 1800 года были переведены Украинская, Днестровская и Брестская инспекции. Под руководством Кутузова около Владимира-Волынского формировалась большая армия численностью в 75 тысяч человек.