58-я армия первого формирования создана 10 ноября 1941 г. (директива Ставки ВГК от 2 ноября 1941 г.) в Сибирском военном округе с непосредственным подчинением Ставке ВГК. В ее состав вошли 362, 364, 368, 370, 380, 384-я стрелковые и 77-я кавалерийская дивизии. После сформирования передислоцирована на территорию Архангельского военного округа для развертывания работ по оборудованию оборонительного рубежа на берегу Мариинского канала от Онежского озера до озера Белое.

В конце мая 1942 г. переформирована в 3-ю танковую армию.

Командующие: генерал-лейтенант Кузнецов В.И. (ноябрь 1941 г.); полковник Москвин Н.А. (ноябрь 1941 г. — май 1942 г.).

Члены Военного совета: бригадный комиссар Воробьев Я.С. (ноябрь 1941 г. -январь 1942 г.); полковой комиссар Яшечкин Ф.В. (январь-февраль 1942 г.); бригадный комиссар Бобров А.Ф. (март-май 1942 г.).

Начальники штаба: генерал-майор Москвин Н.А. (ноябрь 1941 г.); полковник Журавлев К.А. (ноябрь 1941 г. — май 1942 г.).

58-я армия второго формирования создана 25 июня 1942 г. (директива Ставки ВГК от 17 июня 1942 г.) на Калининском фронте. В нее вошли 16-я, 27-я гвардейские, 215-я, 375-я стрелковые дивизии, 35-я и 81-я танковые бригады. С 20 июня армия находилась во фронтовом резерве в районе г. Осташков.

В начале августа 1942 г. полевое управление и войска 58-й армии были обращены на формирование 39-й армии.

Командующий генерал-майор Зыгин А.И. (июнь-август 1942 г).

Член Военного совета бригадный комиссар Савкин В.Г. (июнь-август 1942 г.).

Начальник штаба полковник Ильиных П.Ф. (июнь-август 1942 г.).

58-я армия третьего формирования создана 30 августа 1942 г. (директива Ставки ВГК от 23 августа 1942 г.) в составе Закавказского фронта 2-го формирования. Ее полевое управление было создано на базе полевого управления 24-й армии. Имея первоначально в своем составе 317, 328 и 337-ю стрелковые дивизии, Махачкалинскую дивизию НКВД, 3-ю стрелковую бригаду, ряд артиллерийских и инженерных частей, армия выполняла задачу по оборудованию оборонительного рубежа в районе Махачкалы. В конце ноября 1942 г. ее основные силы были перегруппированы на р. Терек в район Малгобека, где в течение декабря вели оборонительные бои на рубеже Моздок, Верхний Курп. Одновременно силами стрелковой дивизии продолжала оборонять район Махачкалы. В январе 1943 г. 58-я армия в составе Северной группы войск Закавказского фронта участвовала в наступательной операции на ставропольском направлении с целью разгрома немецкой группы армий «А» и освобождения Северного Кавказа. Перейдя в наступление 1 января, войска армии форсировали р. Терек и 3 января освободили города Моздок и Малгобек. Продолжая наступление в общем направлении на Прохладный, Минеральные Воды, армия к 24 января вышла в район севернее Новоалександровской (70 км северо-западнее г. Армавир), где была переподчинена Северо-Кавказскому фронту. В ходе дальнейшего наступления ее войска в начале февраля вышли на побережье Азовского моря. Затем в составе главной ударной группировки фронта принимали участие в Краснодарской операции. Преодолевая ожесточенное сопротивление противника в приазовских плавнях, в условиях непрерывных дождей соединения 58-й армии к концу операции вышли к р. Протока. Во второй половине марта они продолжали вести наступательные бои и к 4 апреля вышли на подступы к г. Темрюк. В дальнейшем, до сентября, армия обороняла побережье Азовского моря от Маргартовки до Ачуева.

10 сентября 58-я армия выведена в резерв Ставки ВГК и 15 ноября 1943 г. расформирована. Ее полевое управление обращено на доукомплектование управления Приволжского военного округа.

Командующие: генерал-майор Хоменко В.А. (сентябрь-ноябрь 1942 г.); генерал-майор, с апреля 1943 г. генерал-лейтенант Мельник К.С. (ноябрь 1942 г. — октябрь 1943 г.).

Члены Военного совета: бригадный комиссар Цветаев Н.Н. (сентябрь 1942 г. — апрель 1943 г.); полковник Усенко А.С. (апрель 1943 г.); полковник Грушевой К.С. (апрель-октябрь 1943 г.).

Начальники штаба: генерал-майор Бармин А.И. (сентябрь-октябрь 1942 г.); полковник Васильев А.Ф. (октябрь-декабрь 1942 г.); генерал-майор Филипповский М.С. (декабрь 1942 г. — май 1943 г.); генерал-майор Ермолаев А.Г. (май-октябрь 1943 г.).