After several years in the Artillery, he moved to the Armored Corps, completing his studies in the Mechanization and Motorization Academy in 1937.

[2] In late August 1939, with other cadets, Shtemenko was assigned as a staff officer to the Soviet forces preparing for the Invasion of Poland, and took part in the operation.

After matriculating from the Academy at autumn 1940, Shtemenko's request to be transferred to the new Tank Corps was rejected and he was posted as an aide to General Mikhail Sharokhin, a department chief in the Operations Directorate.

[3] In August 1941, soon after the German invasion, Shtemenko was appointed as Sharokhin's deputy, an office he held until after the Battle of Moscow, when he was assigned as chief of the Near East department.

[3] During February and March 1944, Shtemenko served as the Stavka representative in the 2nd Baltic Front during the campaign to relieve the Siege of Leningrad.

[7] He continued to serve in the General Staff as deputy chief, and was made a candidate member of the Central Committee, a position he held until 1956.

On 10 February 1977, on the 70th anniversary of his birth and 10 months after his death, the Krasnodar Red Banner Military Academy was renamed after him.