Сформирована 17 октября 1941 г. на базе управления войск Северо-Кавказского военного округа. На 3 ноября имела в своем составе 31, 317, 343, 347, 353-ю стрелковые, 302-ю горнострелковую, 62, 64, 68 и 70-ю кавалерийские дивизии, 6-ю танковую бригаду, 81-й отдельный танковый батальон, 7-й дивизион бронепоездов, отдельный Донской отряд кораблей Азовской военной флотилии, авиационные, артиллерийские, инженерные и другие соединения и части.

Первоначально она именовалась 56-й отдельной армией, 22 ноября вошла в состав Южного фронта и выполняла задачу по обороне Ростова-на-Дону с севера и северо-запада. Тяжелые оборонительные бои ее соединения вели 17-21 ноября. Когда противнику ценой больших потерь удалось захватить город, войска армии были вынуждены отойти на левый берег Дона. В ходе Ростовской наступательной операции ее войска во взаимодействии с 9-й армией Южного фронта освободили Ростов-на-Дону (29 ноября). 30 ноября передана Южному фронту и в его составе продолжала наступление. К середине декабря вышла к р. Миус, севернее Таганрога, где перешла к обороне. В марте 1942 г. войска армии возобновили наступление и к концу месяца вышли на подступы к Таганрогу. В апреле — первой половине июля ее соединения вели оборонительные бои на рубеже Ясиновский, Таганрогский залив, восточнее Таганрога. Под ударами превосходящих сил противника были вынуждены отходить и 21 июля заняли оборону на рубеже Ростовского укрепленного района. Обороняя 100-километровый участок фронта, армия в своем составе имела 4 стрелковые дивизии, понесшие значительные потери в предыдущих боях, 4 стрелковые бригады и пулеметно-артиллерийский батальона укрепленного района. Для наступления на них противник развернул две армии, в том числе танковую. Несмотря на героическое сопротивление войск 56-й армии, ему удалось оттеснить их на левый берег Дона и овладеть Ростовом-на-Дону (24 мая). 29 июля армия включена в Северо-Кавказский фронт (с 5 сентября в Черноморскую группу войск Закавказского фронта 2-го формирования). В его составе участвовала в оборонительных сражениях под Краснодаром и на туапсинском направлении. Ожесточенные бои ее войска вели на подступах к Краснодару в районе Пашковской переправы, где мужественно сражались воины 30-й Иркутской стрелковой дивизии. 12 августа по приказу командования дивизия оставила Краснодар. К 17 августа войска армии отошли на рубеж Безымянная, Крепостная, Дербентская (50 км восточнее Новороссийска), который удерживали до перехода в наступление. В сентябре-декабре 1942 г. соединения армии с 18-й и 47-й армиями Черноморской группы войск оборонялись на туапсинском направлении.

В ходе Северо-Кавказской стратегической операции в январе 1943 г. армия наступала на направлении главного удара Черноморской группы войск Закавказского фронта. К 24 января вышла на подступы к Краснодару и, встретив возросшее сопротивление противника, временно перешла к обороне. С 6 февраля во взаимодействии с другими силами Черноморской группы войск действовала в составе Северо-Кавказского фронта 2-го формирования. В Краснодарской операции 1943 г. ее войска наступали южнее р. Кубань на станицу Крымская. Преодолев ожесточенное сопротивление противника, к 11 марта вышли к заранее подготовленному рубежу обороны немецких войск. Попытка прорыва успеха не имела. В сентябре-октябре армия участвовала в Новороссийско-Таманской операции. В ходе ее в результате упорных боев прорвала оборону противника на «Голубой линии», последовательно преодолела 5 сильно укрепленных промежуточных оборонительных рубежей и 9 октября во взаимодействии с другими войсками Северо-Кавказского фронта освободила Таманский полуостров. В ноябре принимала участие в Керченско-Эльтигенской десантной операции, в ходе которой ее первый десантный эшелон в ночь на 3 ноября силами Азовской военной флотилии был высажен на восточное побережье Керченского полуострова. В последующем, после высадки других десантных эшелонов, войска армии успешно вели наступательные бои по захвату плацдарма, заняли Аджимушкай, к исходу 11 ноября подошли к Булганаку и северо-восточным окраинам Керчи. Встретив ожесточенное сопротивление резервов противника на заранее подготовленных позициях, после неоднократных попыток развить наступление армия перешла к обороне.

20 ноября 1943 г. на базе 56-й армии сформирована Отдельная Приморская армия. В период переформирования армия находилась в непосредственном подчинении Ставки ВГК.

Командующие: генерал-лейтенант Ремезов Ф.М. (ноябрь-декабрь 1941 г.); генерал-майор Цыганов В.В. (декабрь 1941 г. — июль 1942 г.); генерал-майор Рыжов А.И. (июль 1942 г. — январь 1943 г.); генерал-майор, с апреля 1943 г. генерал-лейтенант Гречко А.А. (январь-октябрь 1943 г.); генерал-лейтенант Мельник К.С. (октябрь-ноябрь 1943 г.).

Члены Военного совета: корпусной комиссар Мельников С.И. (ноябрь-декабрь 1941 г.); бригадный комиссар, с ноября 1942 г. полковник Комаров Г.А. (декабрь 1941 г.-январь 1943 г.); бригадный комиссар Гольдинштейн Я.В. (январь-март 1943 г.); полковник Мальцев Е.Е. (март- ноябрь 1943 г.).

Начальники штаба: полковник Бармин А.И. (ноябрь 1941 г.); генерал-майор Арушанян Б.И. (ноябрь 1941 г. — июнь 1942 г.); полковник, с марта 1944 г. генерал-майор Чирков П.М. (июнь-сентябрь 1942 г.); генерал-майор Иванов Н.П. (сентябрь — ноябрь 1942 г.); полковник Кристальный Н.С. (ноябрь 1942 г. — январь 1943 г.); генерал-майор Харитонов А.А. (январь-ноябрь 1943 г.).