Народився в козачій станиці Урюпінській (нині місто Урюпінськ) у селянській родині. Після закінчення школи в 1924 році пішов в місто на заробітки. У 1926 році добровільно пішов в Червону Армію. Закінчив Севастопольську школу зенітної артилерії (1930), Військову академію механізації і моторизації РСЧА (1937), Військову академію Генштабу (1940).
У 1930-33 роках командир взводу, потім командир і політрук батареї, начальник штабу окремого артилерійського дивізіону, перший помічник начальника штабу артилерійського полку. З грудня 1937 року — командир окремого навчального танкового батальйону.
У 1939 році, у складі великої групи слухачів академії Генштабу, брав участь в агресії проти Польщі та «звільненні» Західної України — в штабі Київського особливого військового округу (а з виділенням з окружного управління польового управління Українського фронту — в штабі фронту), у розпорядженні начальника бронетанкових військ округу Я. М. Федоренко. Під час радянсько-фінляндської війни — в числі великої групи слухачів академії Генштабу, що були взяті на посилення Оперативного управління Генерального штабу і проводили одночасно з навчанням в академії чергування в Генштабі для отримання досвіду оперативної роботи.
Восени 1940 року після складання державних іспитів у Військовій академії Генштабу направлений в Оперативне управління Генштабу — старший помічник начальника відділу.
Під час Німецько-радянської війни:
з серпня 1941 — заступник начальника напряму Оперативного управління Генштабу;
з червня 1942 — начальник напряму Оперативного управління Генштабу;
з квітня 1943 — перший заступник начальника Оперативного управління Генштабу;
з травня 1943 — начальник Оперативного управління Генштабу; брав участь в плануванні операцій і здійсненні задумів Верховного Головнокомандування по розгрому збройних сил фашистської Німеччини і мілітаристської Японії. За завданням Ставки ВГК виїжджав на фронти для надання допомоги в організації і проведенні операцій;
у листопаді 1943, під час Тегеранської конференції, Штеменко супроводжував Верховного Головнокомандувача в Тегеран, забезпечуючи його необхідними даними про положення на фронтах;
наприкінці 1943 брав участь в підготовці операції Окремої Приморської армії по звільненню Криму;
у лютому-березні 1944 як начальник штабу при представнику Ставки С. К. Тимошенко знаходився на 2-му Прибалтійському фронті, брав участь в організації прориву оборони німецько-фашистських військ і узгодження дій 1-го і 2-го Прибалтійського фронтів;
у квітні 1944 як представник Ставки виїжджав на Західний фронт (з 24 червня — 3-й Білоруський фронт);
у червні 1944 знаходився на 2-му Білоруському фронті, вніс істотний вклад в підготовку і проведення Могильовської операції 1944, в липні знаходився на 3-му Прибалтійському фронті, надаючи допомогу командуванню в плануванні, підготовці і здійсненні Псковсько-Островської операції 1944.
Після війни
з квітня 1946 — начальник Головного управління і заступник начальника Генштабу;
з листопада 1948 по червень 1952 — начальник Генштабу, заступник міністра Збройних Сил СРСР (з лютого 1950 — військового міністра СРСР);
з червня 1952 по березень 1953 — начальник штабу Групи радянських військ в Німеччині;
з березня по червень 1953 — заступник начальника Генштабу;
У червні 1953 р. після арешту Л. П. Берії понижений у військовому званні з генерала армії до генерал-лейтенанта і призначений начальником штабу Західно-сибірського (з 4 січня 1956 р. Сибірського) військового округу.
з серпня 1956 — начальник Головного розвідувального управління Генштабу, присвоєно звання генерал-полковника. У жовтні 1957 року попередив міністра оборони маршала Жукова, що знаходився у відрядженні в Югославії, про підготовлюване його зміщення.
у 1957 знижений в званні з генерал-полковника до генерал-лейтенанта і призначений першим заступником командувача військами Приволзького військового округу, а літом 1961 р. переведений на таку ж посаду в Закавказький військовий округ;
з липня 1962 — начальник Головного штабу сухопутних військ — перший заступник головнокомандувача Сухопутними військами;
з квітня 1964 — начальник Головного організаційно-мобілізаційного управління — заступник начальника Генштабу;
у лютому 1968 р. С. М. Штеменко повторно присвоюється звання генерал армії;
з серпня 1968 — перший заступник начальника Генштабу — начальник Штабу Об'єднаних збройних сил держав — учасників Варшавського договору.
Член ВКП(б) з 1930 року, в 1952—1956 роках кандидат в члени ЦК КПРС.
Нагороджений орденом Леніна, трьома орденами Червоного Прапора, двома орденами Суворова 1-го ступеня, орденом Кутузова 1-го ступеня, Суворова 2-го ступеня, орденом Трудового Червоного Прапора, Червоної Зірки, «За службу Батьківщині в Збройних Силах СРСР» 3-го ступеня а також іноземними орденами і медалями.
Праці
«Генеральный штаб в годы Великой Отечественной войны» (М., 1968)
«Последние шесть месяцев Второй мировой войны» (М., 1973)
«Освободительная миссия Советской армии» (М., 1975)
.svg){kind=small}
.svg)