Сын камергера и сенатора Матвея Фёдоровича Толстого (1772—1815) и Прасковьи Михайловны (1777—1844), старшей дочери М. И. Голенищева-Кутузова. Родился 2 декабря 1800 года, был крестником императора Павла I, в младенчестве получил звание поручика и был награждён орденом Иоанна Иерусалимского.
С 1821 года адъютант А. Х. Бенкендорфа, 1822 году переведён в Кавалергардский полк поручиком, с 1827 года штабс-ротмистр.
В 1828 году служил при Главной квартире армии на Балканском фронте.
С 1829 года ротмистр, в 1832 году стал адъютантом императора.
С 1836 года полковник, с 1841 года генерал-майор, член Совета Государственного Контроля.
В 1841 году в связи с состоянием здоровья вышел в отставку. Действительный статский советник.
В 1860 году владел 5000 гектаров и 1400 душами в Подольском (Покровское) и Бронницком уездах.Так как Михаил Илларионович Кутузов не оставил потомства по мужской линии, то фамилия Голенищев-Кутузов была передана указом в 1859 году его внуку генерал-майору Павлу Матвеевичу Толстому «и в потомство его к старшему в роде» . Принимал деятельное участие в воспитании своих рано осиротевших племянников Ивана и Дмитрия.Его портрет кисти Владимира Гау находится в краеведческом музее Моршанска. Оставил воспоминания о подавлении восстания декабристов, опубликованные в «Русском архиве» в 1882 году.