Trzecie formowanie Po raz trzeci armia została sformowana 30 sierpnia 1942 roku w ramach Frontu Zakaukaskiego na bazie 24 Armii. W skład armii wchodziły początkowo dowództwo, 317., 328., 337 Dywizja Strzelecka, Machaczkalska Dywizja Strzelecka NKWD, 3 Brygada Strzelecka, jednostki artylerii i inżynieryjne. Armia stacjonowała na terenie Czeczenii i Dagestanu, gdzie tworzyła linie obronne i walczyła z antyradzieckimi grupami rebeliantów. Pod koniec listopada 1942 roki jej główne siły zostały przegrupowane nad rzeką Terek w rejonie Małgobeku, gdzie w grudniu toczyły walki obronne na linii Mozdok – Wierchni Kurp.
W styczniu 58 Armia wzięła udział w sowieckiej kontrofensywie na Północnym Kaukazie. Przechodząc do ofensywy 1 stycznia 1943 roku, oddziały armii przekroczyły rzekę Terek i 3 stycznia wyzwoliły miasta Mozdok oraz Małgobek. Kontynuując pościg za wycofującym się wrogiem wraz z innymi formacjami Frontu Zakaukaskiego w kierunku na Prochładny i Mineralne Wody, do 24 stycznia armia dotarła w rejon na północ od Nowoaleksandrowska, gdzie została przeniesiona na Front Północno-Kaukaski.