Первым начальником штаба 56-й Отдельной армии стал полковник Александр Иванович Бармин, занимавший аналогичную должность в СКВО. Но вскоре, 7 ноября 1941 г., начальником штаба был назначен генерал-майор Баграт Исаакович Арушанян. Он родился в 1903 г. в Эриванской губернии (сейчас – Республика Армения). С 1923 г. – в рядах РККА, с 1931 г. – в ВКП(б). Окончил Армянскую объединенную военную школу и Военную академию имени М. В. Фрунзе, занимал различные командные и штабные должности, участвовал в советско-финской войне. Начало Великой Отечественной войны встретил начальником штаба 12-й армии Юго-Западного фронта, погибшей в Уманском котле. Самому Арушаняну с группой из пяти бойцов в начале сентября удалось выйти в расположение советских войск, и 13 октября он был назначен заместителем командующего Юго-Западным фронтом по тылу.

Заместителями командующего 56-й Отдельной армией были утверждены генерал-майоры П. М. Козлов и А. А. Гречкин. Петр Михайлович Козлов родился в 1893 г. в Пятигорске, в 1914 г. был призван в армию. Участвовал в Первой мировой войне на Кавказском фронте, стал командиром взвода. В 1917 г. вступил в РСДРП(б) и Красную гвардию, в 1918 г. – в РККА. В годы Гражданской войны командовал отрядом, полком, бригадой. После войны продолжил службу, окончил Военную академию имени М. В. Фрунзе. В 1937 г. был арестован, но в следующем году освобожден. Начало войны встретил в должности начальника курса Академии Генерального штаба РККА. После неоднократных просьб отправить на фронт был назначен заместителем командующего 56-й Отдельной армией по тылу.

Александр Алексеевич Гречкин родился в 1893 г. в селе Карпенка (в настоящее время – Самарской области). С 1914 г. служил в Русской императорской армии, участвовал в Первой мировой войне. Революцию штабс-капитан Гречкин встретил в должности командира батальона. В РККА вступил в 1918 г., командовал стрелковым батальоном и запасным полком. После Гражданской войны занимал различные должности, был командиром батальона, дивизии, помощником командира корпуса. Окончил курсы усовершенствования командного состава РККА «Выстрел», участвовал в борьбе против басмачей в Туркестане и советско-финской войне. Войну встретил в должности помощника командующего войсками СКВО по военно-учебным заведениям. Став начальником гарнизона Ростова-на-Дону, руководил работами по созданию прикрывавших его оборонительных рубежей. Почти месяц, с 3 августа по 4 сентября 1941 г., временно исполнял обязанности командующего войсками СКВО.

Командующим артиллерией 56-й армии стал генерал-майор Георгий Спиридонович Кариофилли. Грек по национальности, он родился в 1901 г., вступил в РККА в 1918 г., в РКП(б) – в 1919 г., участвовал в Гражданской войне. Окончил Военную академию имени М. В. Фрунзе, был командиром артиллерийского полка, начальником артиллерии дивизии, корпуса, заместителем начальника артиллерии военного округа. В начале войны занимал должность начальника штаба артиллерии Западного фронта, с августа 1941 г. стал начальником артиллерии СКВО.

ВВС армии возглавил генерал-майор Степан Акимович Красовский. Белорус Красовский родился в 1897 г. в деревне Глухи Могилевской губернии (в настоящее время – Могилевской области Республики Беларусь). С 1916 г. в звании унтер-офицера участвовал в Первой мировой войне. В 1917 г. вступил в Красную гвардию, в 1918 г. – в РККА. В годы Гражданской войны был начальником связи авиаотряда, летчиком-наблюдателем, комиссаром авиационного отряда. После войны окончил курсы усовершенствования начсостава ВВС, Военно-воздушную инженерную академию имени Н. Е. Жуковского. Участвовал в советско-финской войне, командовал ВВС 13-й армии и Мурманской авиабригадой. Затем был начальником Краснодарского военного авиационного училища, помощником командующего ВВС СКВО по военно-учебным заведениям, с июня 1941 г. – командующим ВВС СКВО.