Tolstoy worked for a time in for the French daily Le Monde and then for Agence France-Presse as a Moscow correspondent.

In September 2016, he was elected to the State Duma from the Lyublino constituency #199 of Moscow, running from the political party United Russia.

The sanction applied only to Russian parliamentarians in PACE, the Council of Europe's parliamentary body, and Russia continued to be a full member of the organisation as a whole.

In response, the Russian parliamentary delegation suspended its co-operation with PACE in June 2014, and in January 2016 – despite the lapsing of the sanctions – the Russian parliament decided not to submit its delegation's credentials for ratification, effectively leaving its seats empty.

On 25 June 2019, after an eight-hour debate which ended in the small hours, the Assembly voted to change its rules,[15] to make clear that its members should always have the right "to vote, to speak and to be represented", acceding to a key Russian demand and paving the way for the return of a Russian parliamentary delegation.

[17][18] As a result, the Russian delegation which included returned to PACE with its full rights after a gap of five years.

In October 2022, because of recent nuclear threats made by Moscow, the Council of Europe adopted a stinging rebuke to Tolstoy declaring Russia a "terrorist" regime.