Сближение между Толстым и Меншиковым произошло после 1714 года, по возвращении Петра Андреевича из Стамбула в Петербург.

Первые письма Толстого к Меншикову датированы 1716 годом, когда Толстой сопровождал царя в заграничной поездке. Уже тогда в переписке улавливаются близкие отношения между ними. И если дружба с Шереметевым складывалась в годы расцвета фавора Александра Даниловича, его наибольшей близости царю, то приятельские отношения с Толстым относятся к годам падения влияния Меншикова, когда Александру Даниловичу самому приходилось искать заступничества и он искал его у людей, чье влияние при дворе возрастало. Толстой как раз и принадлежал к таким людям.

Что за услуги оказывал Меншиков Толстому, неизвестно. Но ими тот пользовался довольно часто, ибо то и дело благодарил светлейшего. «Премного… благодарствую за высокую вашей светлости милость к домашним моим», – писал Толстой в 1716 году, а в 1717 году из Парижа благодарил «за прочие милостивые к дому моему призрения». В 1719-м из Берлина изъявлял благодарность за «обещание о содержании в милости своей домашних моих».

В других случаях Толстой просил оказать внимание, но в чем оно состояло – неясно: «О чем будет просить сын мой Иван, благоволи показать в том милость и великое споможение»; в другой раз он просил «содержать во своей милости сына моего Ивана, как мне изволили милостиво обещать». Лишь однажды просьба была конкретной: взрыв порохового погреба в Петербурге разрушил дом Толстого, и Петр Андреевич просил петербургского губернатора помочь восстановить дом: «… дать мне работников для собрания разметанного двора моего». Одна просьба принадлежит к числу исключительных. С ней Толстой обратился из Вены, где находился проездом в связи с делом царевича Алексея.

Петр Андреевич не без основания считал, что его усердие, приложенное к возвращению царевича на родину, далеко не все в России оценят одинаково. Рвение Толстого в одних кругах вызывало одобрение, в других – осуждение и, быть может, желание выразить ему свое нерасположение какой-либо враждебной акцией. 21 августа 1717 года он отправил из Вены письмо, в котором наряду с обычной просьбой «содержать меня в высокой своей милости» имеется просьба защитить его от нападок недоброжелателей: «… в прибытии его царского величества в С.-Питербурх милостиво меня охранить, ежели кто из немилостивых ко мне похочет мене чем вредить».

Участие Меншикова и Толстого в деле царевича Алексея, несомненно, скрепило их отношения более тесными узами. После гибели царевича летом 1718 года наступила пора наибольшей близости: Толстой без риска вызвать раздражение обращался к Меншикову с ходатайствами не только за себя и своих родственников, но и приятелей и даже знакомых. В архиве сохранилось несколько исключительных по ценности цидулок, передающих с поразительной непосредственностью и яркостью дух времени:

«Прошу вашу светлость о сем листоподавце, сотвори к нему милость в прошении ево, понеже отец ево – приятель мне – и убедил меня просить об нем вашу светлость». Еще более выразительна другая цидулка, полученная Меншиковым в том же 1718 году. В ней Толстой обратился к Меншикову за конкретной «милостью», чтобы тот пристроил «листоподавца» на доходное место провиантмейстера. «Понеже, – мотивировал свою просьбу Петр Андреевич, – того чина достоин». Основание прежнее: «… понеже отец ево мне добрый приятель и свойственник».