После кончины вождя пришедший к власти Никита Сергеевич Хрущев не без помощи лизоблюдов из военного ведомства, мгновенно сориентировавшихся в складывающейся обстановке и проведших массу интриг, освободил генерала армии Штеменко от занимаемой должности, понизил в воинском звании до полковника и отправил служить в Закавказский военный округ, где на должности начальника штаба войск округа уже находился генерал армии Алексей Иннокентьевич Антонов. Он был возвращен сюда еще в 1946 году. Следует заметить, что Антонов, невзирая на свой исключительный профессионализм и такт, был чем-то неприятен вождю. Известно лишь, что начальник Главного оперативного управления генерал Василевский в 1942 году, и то с третьей попытки, убедил Сталина в целесообразности перевода из Закавказского военного округа начальника штаба генерала Антонова в Москву. Но, как оказалось, ненадолго…
Теперь Антонов, встретив в штабе войск округа своего недавнего подчиненного, сразу же предложил ему должность своего заместителя и начальника оперативного отдела штаба округа. Алексей Иннокентьевич питал добрые чувства к Штеменко не только как к профессионалу, но и как к надежному человеку, с которым хватил не один фунт штабного лиха. Не следует исключать и того, что генерал армии Антонов рассчитывал, что благодаря своему такту, дару убеждения и прозорливости он все-таки сумеет в кратчайшие сроки подвести базу к тому, чтобы столь незаслуженно наказанный коллега по военной службе был восстановлен в своем высоком воинском звании.
Но не тут-то было.
В Москве внимательно следили за новыми опальными военачальниками, контролируя каждый их шаг.
За десять следующих лет Сергею Матвеевичу пришлось вновь последовательно пройти все ступеньки соответствующих воинских званий и должностей и в июле 1962 года в силу сложившихся обстоятельств (очевидно, сработали все-таки прозорливость и усилия Антонова, работавшего в это время в должности начальника штаба Объединенных Вооруженных Сил государств– участников Варшавского Договора) Штеменко – уже генерал-полковник– был назначен первым заместителем Главнокомандующего Сухопутными войсками. На должности, соответствующей тогда воинскому званию генерал армии. Но до возвращения ему этого воинского звания было еще более шести лет!
В апреле 1964 года Штеменко назначается заместителем начальника Генштаба ВС СССР, а в августе 1968-го, когда у власти находился Леонид Ильич Брежнев, он был восстановлен в воинском звании генерал армии и назначен начальником штаба Объединенных Вооруженных Сил государств – участников Варшавского Договора.