Жена 1820-е
Надежда Сергеевна Хитрово * 1800 † 24.12.1831
Жена 11.11.1835
Мария Константиновна Бенкендорф * 1818 † 31.10.1844
Дети
Наталья Павловна Толстая * 14.10.1836 † 25.06.1839
Константин Павлович Толстой * нач. 1843 † 1848
Павел Павлович * 8.12.1843 † 22.04.1914

Старшие братья
Илларион Матвеевич Толстой * 28.05.1798 † 18.01.1821
Федор Матвеевич Толстой * 19.06.1799 † 23.12.1821
Мл. братья и сёстры
Николай Матвеевич Толстой * 7.05.1802 † 25.12.1879
Гавриил Матвеевич Толстой * 23.07.1803 † 1848
гр. Иван Матвеевич Толстой * 20.03.1806 † 21.09.1867
Анна Матвеевна Толстая * 9.01.1809 † 18.01.1897
Феофил Матвеевич Толстой * 6.07.1810 † 20.02.1881
Екатерина Матвеевна Толстая * 28.03.1814 † 17.12.1898
Алексей Матвеевич Толстой * 1810-е
Григорий Матвеевич Толстой * 25.01.1816 † 23.02.1870

Отец
Матвей Федорович Толстой * 29.03.1772 † 20.11.1815
Мать
Прасковья Михайловна Голенищева-Кутузова * 11.01.1777 † 2.01.1844

с 1859 разрешено присоединить фамилию деда с передачей старшему в роду представителю мужского пола