Tolstoy was aide-de-camp to general Alexander von Neidgart, and was stationed in Laibach (Ljubljana) during the Congress, where he was appointed head of the Russian headquarters of the detachment against Piedmont.

In 1826, Count Tolstoy participated in the Russo-Persian War, 1826–1828, serving as aide de camp to Mayor-General Prince Aleksandr Sergeyevich Menshikov.

He was awarded with a golden sword for the restoration of the communication between the main army and the corps of general Loggin Rot in July of the same year; and was wounded in the head during the Siege of Varna.

In 1831, Yegor Tolstoy participated in the military actions against Polish rebels during November Uprising and was awarded with an Order of St. Vladimir of the 3rd degree for the seizure of Warsaw.

Tolstoy held this office until September 1856 and participated in the defense of the city from bombardments and landing operations during the Siege of Taganrog in 1855.