In 1837, Shestakov participated in the landing operation near Cape Konstantinovsky for which he was decorated with an order and promoted to the rank of midshipman.

In 1838, he was on board the corvette Ifigeniya, participated in the landing operation near Shanedho, and was decorated with an Order of St. Anna of 4th degree.

On April 11, 1843 (Old Style) Admiral Mikhail Lazarev made him his aide-de-camp for two years and promoted him to the rank of lieutenant.

Upon his return to Russia in February 1854, he was assigned to the steamship committee and promoted to the rank of 2-rank captain and transferred to the Baltic Fleet.

In 1860–1862 - commander of a squadron of Russian ships in Mediterranean Sea near the coastline of Syria to protect Christians during the massacres in Lebanon.

Shestakov initiated the establishment of the first naval school in 1868 that opened later during governorship of Johan Hampus Furuhjelm in 1874.

He published several articles under his real name and under the penname Excelsior in the naval journal Morskoy Sbornik (Морской Сборник) in 1850, 1854-1861, 1864 and 1871.

Shestakov translated William James's The Naval History of Great Britain into the Russian language.

In 1873 he published his book of memoirs under the title The Half-century of Ordinary Life (Полвека обыкновеннй жизни).