Тем не менее Голенищев-Кутузов принял участие в антипавловском заговоре, арестовав в ночь с 11 на 12 марта 1801 г. преданного императору шефа своего полка А. С. Кологривова. Видимо, в награду за проявленное рвение, через пять дней после вступления на престол Александра I Павел Васильевич стал командиром самого престижного полка российской конницы – Кавалергардского.
В 1806—1809 гг. во главе Белорусского гусарского полка участвовал в войне с Турцией. После недолгой отставки («по причине расстроенного здоровья») вернулся на службу и в 1810 г. был назначен обер-полицмейстером Петербурга. Под его началом стражи порядка с особым рвением отлавливали пьяниц и нарушителей общественного порядка, причем некоторые филологи утверждают, что слово «кутузка» (место, куда тащили задержанных) ведет свое происхождение именно от фамилии Кутузов.
В 1811 г. ушел в отставку с поста обер-полицмейстера, так как не смог (по собственным словам) «прислуживаться» под началом тогдашнего министра полиции А. Д. Балашева. Во время Отечественной войны успешно командовал созданным из ямщиков партизанским отрядом. Затем участвовал в заграничном походе 1813 г.: сражался при Люцене, Баутцене, Дрездене, Кульме, Лейпциге. 13 апреля 1814 г. доставил в Петербург известие о взятии Парижа. Столичное купечество на радостях поднесло Кутузову на серебряном блюде кружку с четырьмя тысячами червонцев. Блюдо и кружку Павел Васильевич оставил «себе и детям на память незабвенного дня», а червонцы пожертвовал во вновь учрежденное «Сословие призрения разоренных от неприятеля жителей». В последующие годы Кутузов возглавлял военно-учебные заведения, а после смерти М. А. Милорадовича занял пост столичного генерал-губернатора. Именно он руководил казнью пяти декабристов на Кронверкском валу Петропавловской крепости. Трое из них сорвались с виселицы, и Павел Васильевич мог бы прервать церемонию, поскольку издревле существовал обычай, что если осужденный таким образом избегал казни, то смертный приговор ему отменяли. Однако генерал-губернатор без малейших сомнений скомандовал: «Вешать снова!»
В правление Кутузова был осуществлен целый ряд строительных и хозяйственных мероприятий. В 1826 г. на Большой Морской улице (где жил генерал-губернатор) устроили «особые колеи-колесо-проводы», ставшие предшественниками более поздних трамвайных рельсов. Начался период активного строительства мостов через петербургские реки и каналы. В 1827 г. в Санкт-Петербурге возникло первое в России страховое общество, а на набережной реки Крестовки возвели Каменностровский театр. Однако в этот же период усилилась роль полицейских структур в жизни города. Возникла тайная политическая полиция – III отделение, а сам Павел Васильевич значительную часть своего времени посвящал надзору за настроениями в обществе и «перевоспитыванию» неблагонадежных литераторов и журналистов.
В 1830 г. из-за ухудшившегося здоровья Кутузов подал в отставку с поста генерал-губернатора. Через два года Николай I наградил его графским титулом, однако к активной административной деятельности он так и не вернулся. Скончался Павел Васильевич 1 ноября 1843 г. и был похоронен в родовом селе Шубине Тверской губернии.