Милютин принялся за работу весьма деятельно. Он заметил, что в военном управлении на Кавказе в течение полувека сложились своеобразные округа или местные отделы, крупные и мелкие, без единого плана, что при существовании разбухшего аппарата наместника функционирует также и слабая сеть местных военных органов, а это давало широкий простор злоупотреблениям, поскольку военные должности в соответствии с идеей «военно-народного управления» зачастую совмещались с гражданскими. По инициативе Д.А. Милютина правое крыло кавказского наместничества было преобразовано в Кубанскую область, левое – в Терскую, Лезгинская кордонная линия упразднялась, а в июне 1860 г. образованы Дагестанская область и Закатальский край. В конце 1857 г. Отдельный Кавказский корпус был, как уже отмечалось, преобразован в Кавказскую армию, на которую распространялись основные положения о полевом управления 1 – й (Действующей) армии. Значительную самостоятельность по отношению к провиантскому департаменту Военного министерства официально получило провиантское ведомство Кавказской армии.
Основная идея всех этих изменений состояла в том, что каждый из местных воинских начальников получал известную самостоятельность в военном управлении на правах командира не-отдельного корпуса, а также гражданское управление с правами генерал-губернатора. Иными словами, в разумных пределах осуществлялся принцип децентрализации власти. Во главе Кавказской армии стоял главнокомандующий, ему подчинялся начальник главного штаба, в ведении которого находились управления дежурного генерала, генерал-квартирмейстера, начальника артиллерии, начальника инженеров, генерал-аудиториат.
Эти и другие преобразования Д.А. Милютина значительно расширили самостоятельность кавказской администрации и способствовали успехам русских войск в боевых действиях по завершению Кавказской войны. Вместе с тем реформы требовали определенных затрат. Стремясь к скорейшему завершению Кавказской войны, Александр II понимал их необходимость, хотя и напоминал постоянно А.И. Барятинскому не забывать об экономии государственных средств. Несколько иначе относилось к реформам на Кавказе Военное министерство Н.О. Сухозанета, желавшее держать Кавказскую армию под своим полным контролем. Когда в конце 1857 г. Д.А. Милютин прибыл в Петербург для утверждения проекта «Положения об управлении Кавказской армией», военный министр усмотрел в этом проекте противоречие с общими принципами организации военного управления, основанными на крайней централизации, и выступил против. Обсуждение вопроса Александр II, покровитель генерала Барятинского, вынес на заседание одного из департаментов Сената – Кавказского комитета, что и решило судьбу проекта.
Как начальник главного штаба Кавказской армии Д.А. Милютин занимался и оперативными делами, поэтому в реорганизации местной военной администрации он сделал не очень много (к тому же пробыл в должности менее четырех лет). Тем не менее устройство русских войск на Кавказе послужило