In 1827–1830 lieutenant Voyevodsky served on Jezekiel, a ship-of-the-line of count Login Geiden's Mediterranean squadron; he participated in the Battle of Navarino in October 1827 and in the naval blockade of the Dardanelles during the Russo-Turkish War of 1828–1829.
After four peaceful seasons with the Baltic Fleet (1830–1834) Voyevodsky was transferred from the Navy to the Russian-American Company.
By 1849 he attained the rank of captain (Russian: капитан первого ранга) and was in command of a ship-of-the-line.
In the beginning of the Crimean War (July 1853), Voyevodsky was appointed Governor of Russian America.
Voyevodsky attained the rank of full admiral in 1877; he died in Saint Petersburg and was buried at the Smolenskoye Cemetery.