В канун Второй мировой войны, в 1937-м, Сергей Матвеевич закончил Военную академию механизации и моторизации РККА. А в 1940-м после окончания Академии Генштаба был он определен на службу в этот высший рабочий орган Наркомата обороны (НКО). В августе 1941 был назначен на должность заместителя начальника направления, затем он же его возглавил и руководил до апреля 1943 года. За это время последовательно был удостоен воинских званий генерал-майор и генерал-лейтенант. Затем стал первым замом, а через месяц начальником оперативного управления Генштаба. В том же году был удостоен воинского звания генерал-полковник.

Штеменко пользовался особым уважением и авторитетом как высокопрофессиональный оператор военного искусства у Верховного Главнокомандующего и как правило, с его согласия, прежде чем приступить к разработке той или иной стратегической операции, отправлялся на фронт для изучения обстановки на месте.

Так, в 1943 г. он был направлен в Отдельную Приморскую армию в группе Маршала Советского Союза Климента Ефремовича Ворошилова. После проведенного Военного совета, в котором участвовали представители Северо-Кавказского направления, Черноморского флота, командования Отдельной армии и других войск, был составлен проект решения. Председательствующий на Военном совете член Политбюро ЦК ВКП(б) Ворошилов внес предложение, что столь ответственный документ должны подписать командующие, члены Военного совета и начальники штабов. В итоге получилось десять подписей.

На что Сергей Матвеевич заметил: «Климент Ефремович, столь ответственный документ не следует подписывать таким большим количеством людей».

Реплика вызвала неудовольствие маршала: «Вы не уважаете участников совещания, молодой человек!»

Генерал-полковник сделал последнюю попытку исправить ситуацию: «Товарищ маршал, документ должен быть подписан вами и мной как представителями Ставки и Генштаба. В противном случае… это крайне не понравится товарищу Сталину».

Но, несмотря на прозвучавшее имя, довод Ворошилову показался неубедительным и документ с десятью подписями оказался на столе у Верховного Главнокомандующего.

По истечении времени, когда замысел операции был воплощен в жизнь, и войска 4-го Украинского фронта, Приморской Отдельной армии Черноморского флота освободили Крым и Севастополь от гитлеровских захватчиков, 9 мая 1944 года Верховный Главнокомандующий отметил участников боев и разработчиков операции соответствующими знаками внимания. Многие получили весьма высокие полководческие награды; при этом первый заместитель начальника Генштаба Алексей Иннокентьевич Антонов представил и своего подчиненного генерала Штеменко к ордену Суворова 1-й степени.

Когда Антонов вошел в кабинет вождя и доложил ситуацию на фронтах, он заметил выражение удовлетворения на лице Сталина. Закурив, тот сказал: «А теперь давайте красную папку». Следует при этом заметить, что руководитель страны никогда не подписывал никаких документов внимательно не изучив их. То же произошло и на этот раз. Он взял «наградную» папку, раскрыл ее и глазами пробежал по списку фамилий; понятное дело, вождь просматривал их и ранее. Вот синий карандаш в руках Сталина остановился напротив фамилии Штеменко, зачеркнул надпись «1-й степени» и сбоку написал: «2-й степени». А вслух Сталин добавил: «Будэт знать, как па-адписывать документы». Так наряду с другими наградами, которых был удостоен Сергей Матвеевич за время своей службы в Вооруженных Силах СССР, рядом с двумя орденами Суворова 1-й степени (платиновыми) стал красоваться Суворов 2-й степени (золотой).