Действительный тайный советник (с 1718). Из древнего дворянского рода. Сын окольничего Андрея Васильевича Толстого (ум. 1690) от брака с дочерью Михаила Васильевича Милославского, дальнего родственника царицы Марии Ильиничны (первой супруги царя Алексея Михайловича). Получил домашнее образование. В 1665—1669 служил при отце, бывшем в то время воеводой в Чернигове. В 1671 пожалован в стольники царицы Натальи Кирилловны, а в 1676— в стольники царя Фёдора Алексеевича. Во ходе русско-турецкой войны 1676—1681 принял участие в Чигиринских походах 1677—1678. После смерти царя Фёдора Алексеевича (апрель 1682) Толстой, как родственник Милославских, встал на сторону царевны Софьи Алексеевны. Современник А. А. Матвеев писал о братьях Толстых как о людях «в уме зело острых и великого пронырства»; они имели прозвище шарпенков. 15.05.1682, в день стрелецкого бунта, Толстой распространял среди стрельцов провокационный слух об умерщвлении Нарышкиными царевича Ивана Алексеевича, чем подвигнул их в поход на Кремль. За услугу, оказанную царевне Софье Алексеевне во время бунта, был пожалован в комнатные стольники к царю Ивану Алексеевичу.
Падение царевны Софьи Алексеевны в 1689 заставило Толстого перейти на сторону царя Петра Алексеевича, однако царь долго относился к нему недоверчиво. Он служил воеводой в Устюге Великом, затем — в Семеновском полку, где получил чин прапорщика, а затем капитана, был переведен в Преображенский полк; участвовал в Азовских походах 1695—1696. Стремясь завоевать доверие Петра I, он в начале 1697, в возрасте 52-х лет, будучи уже дедом, выпросил у царя разрешение отправиться волонтером в Италию для изучения военно-морского дела. Два года, проведенные им в Италии, сблизили его с западноевропейской культурой, он свободно владел итальянским языком. Сохранился дневник заграничного путешествия Толстого, характерный образчик тех впечатлений, какие выносили русские люди петровского времени из своего знакомства с Западной Европой. В январе 1699 возвратился в Москву.
В апреле 1702 назначен первым постоянным послом России в Турции. В 1703 он написал политический и географический обзор «Состояние народа турецкого», а в 1706 - обстоятельное описание Чёрного моря. Пребывание Толстого в Турции пришлось на крайне сложный период в русско-турецких отношениях: турки не могли смириться с потерей Азова, и их все больше беспокоили победы русских над шведами. Толстому приходилось использовать всю свою хитрость и изворотливость, а также давать взятки турецким чиновникам. Считается, что при этом он не забывал и о своих интересах, а когда один из секретарей посольства захотел донести на него в Россию, Толстой отравил подчиненного (впрочем, эта распространенная легенда восходит к недоброжелателям Толстого из французских дипломатов, болезненно воспринимавших успехи России в Турции). В 1706 он просил сменить его, но Петр его просьбу не удовлетворил. Вел переговоры о выдаче бежавших в Турцию после Полтавской битвы 1709 шведского короля Карла XII и гетмана И.С. Мазепы. В ноябре 1710, когда новая война с Турцией стала неизбежной, Толстой был посажен в Семибашенный замок, где находился до апреля 1712. Выйдя на свободу, он снова просил о разрешении вернуться, и на сей раз это было ему разрешено, однако турки, полагавшие, что Россия не выполняет своих обязательств, его не отпустили. Уже в ноябре того же года он снова попал в темницу и освободился лишь в марте 1713. В июне 1714 был подписан мирный договор, и Толстой смог, наконец, вернуться на родину.
В 1716—1717 сопровождал царя Петра I в поездке по странам Европы, участвовал в дипломатических переговорах. В 1717 Толстому была поручена особенно сложная и ответственная миссия — вести переговоры с австрийским двором о возвращении бежавшего царевича Алексея. Вместе с А. И. Румянцевым Толстой прибыл в Вену, имел аудиенцию у императора и добился его разрешения на поездку в Неаполь, где скрывался царевич. Путем запугивания и ложных обещаний Толстой склонил Алексея к возвращению в Россию. В 1718 принимал деятельное участие в следствии и суде над царевичем и его сообщниками. С этого времени Толстой стал одним из самых близких и доверенных лиц Петра I. В декабре 1717 назначен сенатором. В 1717—1721 президент Коммерц-коллегии. В 1718—1726 первый министр Тайной канцелярии. В декабре 1718 получил чин действительного тайного советника. В 1719 был послан с дипломатическим поручением в Берлин. В марте 1722 пожалован орденом Св. Апостола Андрея Первозванного. В разное время он получил от Петра I 1695 крестьянских дворов (к концу его жизни за ним числилось свыше 12.5 тыс. душ крестьян). Во время Персидского похода 1722—1723 возглавлял походную канцелярию имя. Петра I. Дело царевича Алексея Петровича сблизило его и с императрицей Екатериной Алексеевной, в день коронации которой (7.05.1724) возведён, с нисходящим его потомством, в графское Российская Империи достоинство.
После смерти Петра I (январь 1725) вместе с А.Д. Меншиковым энергично содействовал возведению на престол императрицы Екатерины I. В феврале 1726 стал инициатором создания Верховного тайного совета, в состав которого и был включен. Однако ни доверие императрицы, ни изворотливость и опытность в интригах не уберегли Толстого от падения. Долго действуя заодно с А.Д. Меншиковым, он разошелся с ним по вопросу о преемнике Екатерины I. Если Меншиков вынашивал план возведения на престол сына царевича Алексея Петровича, с условием его женитьбы на одной из своих дочерей, то Толстой, опасаясь, что воцарение сына погибшего при его активном содействии царевича будет вечной угрозой ему и всей его семье, выступал за передачу престола дочерям Петра Великого. В разгоревшейся политической борьбе А.Д. Меншиков одержал верх: в апреле 1727 Толстой был арестован, а в мае он и его сыновья были лишены чинов и графского титула. Вместе с сыном Иваном сослан в Соловецкий монастырь, где и скончался в возрасте 83-х лет; похоронен там же.
Толстой, по отзыву современника Ф.-В. Берхгольца, был веселого и любезного нрава, чрезвычайно вежлив и хорошо говорил по-итальянски. Он очень приятный, остроумный, любезный собеседник. Хрестоматийными стали слова Петра Великого, обращенные к Толстому: «Голова! Голова! Если б ты не так была умна, то давно была бы отсечена!». «Жизнь Толстого примечательна во многих отношениях,— писал историк Н.И. Павленко.— Пётр Андреевич был единственным сподвижником Петра, который начинал свою карьеру его противником, а заканчивал его верным слугой. Чтобы совершить подобную метаморфозу, надобно было преодолеть косность и консерватизм среды, на которую он поначалу ориентировался. В ряды сподвижников Петра Толстой влился в зрелые годы, и, несмотря на это, он с усердием стал постигать новое, причем в процессе не обучения, как это делали его более молодые современники, а переучивания. Это всегда сложно и трудно». Дети Толстого: граф Иван Петрович (ум. 1728), действительный статский советник; граф Пётр Петрович (ум. 1728), полковник. Указом императрицы Елизаветы Петровны в мае 1760 внукам Толстого был возвращен графский титул.
