Приговоренный к смерти умирающей Екатериной, Толстой был помилован новым государем Петром II, получил, как тогда говорили, «вместо смерти живот» и был сослан на Соловки вместе с сыном Иваном, чья вина состояла только в родстве с отцом.

 С давних пор Соловки были местом страшным. Полтора года провел в тюрьме Толстой, а по описи после его смерти видно, что все меха, шубы и одежды заключенного истлели от сырости. Жизнь в каменном мешке Головленковой башни монастыря, где царили темнота, холод и голод, отличалась такой суровостью, что иным узникам каторга на материке казалась раем. 

Позже в своей челобитной один из заключенных Михаил Пархомов, просил, чтобы «вместо сей ссылки в каторжную работу меня (б) отдали, с радостию моей души готов на каторгу, нежели в сем крайсветном, заморском, темном и студеном, прегорьком и прескорбном месте быти». К тому же, как часто бывало со знатными узниками, охрана стремилась унизить, досадить прежде столь гордому вельможе, отравляла жалкое существование его мелочными придирками.

 Толстые выдержали недолго. Уже в конце 1728 года скончался Иван Толстой, а в январе 1729 умер и сам Петр Андреевич. Он пережил почти на год своего заклятого врага и гонителя Меншикова, к этому времени угасавшего на другом пустынном конце империи — в Березове.