Пока же за два месяца военный министр подготовил программу военных преобразований и 15 января 1862 г. представил ее императору. После высочайшего утверждения Милютин твердо и последовательно выполняет эту программу.
Он начал с реформы военного управления. В 1864 г. была упрощена структура Генерального штаба, в который вошли управления упраздненного штаба гвардейского корпуса. Был существенно повышен статус офицеров Генерального штаба, что привело к увеличению желающим служить в нем и численности высокообразованных офицеров.
В 1862–1867 гг. проведена военно-окружная реформа. Были образованы Петербургский, Московский, Казанский, Харьковский, Киевский, Одесский, Виленский, Варшавский, Финляндский, Восточно-Сибирский, Западно-Сибирский, Кавказский, Оренбургский и Туркестанский военные округа. Тем самым, с одной стороны, устранялись неудобства подчинения различных родов войск и военных ведомств разным начальникам в столице – начальникам артиллерии, инженерных войск, комиссариатского и провиантского дела, с другой стороны, устранялась и чрезмерная централизация военного управления. Командующий военным округом получал полномочия по управлению как строевыми частями всех родов войск, так и всеми военными службами, от медицинской и продовольственной до снабженческой и ветеринарной. В случае начала войны штаб округа разворачивался в штаб армии.
С центрального военного аппарата была снята значительная нагрузка. Благодаря этим мерам численность аппарата министерства была сокращена почти на тысячу человек, а объем переписки уменьшился на 45 %. Войска переведены были на сокращенные штаты мирного времени, численность армии сокращена до 743 тысяч человек в 1867 г. Улучшился такой важный показатель, как сроки мобилизации: они сократились с 6 месяцев в 1859 г. до 9-26 дней в 1877 г.
Была разработана Военно-судебная реформа. 15 мая 1867 г. Александр II подписал новый Военно-судебный устав, основные принципы которого были согласованы с системой гражданского судопроизводства. В 1879 г. был утвержден новый Дисциплинарный устав. Для подготовки кадров в 1867 г. была создана Военно-юридическая академия.
Медленнее всего шло изменение системы воинской повинности. Ранее рекрутская система охватывала лишь крестьян и мещан, Милютин намеревался сделать призыв всесословным. Эта идея не сразу была понята государем. С 1862 г. действовала в составе Военного министерства специальная комиссия, но идея равенства всех сословий при несении воинской повинности встречала яростных и упорных противников во всех слоях русского общества. Негодовали и аристократы, и купцы, недовольные, что нельзя будет просто откупиться от солдатчины. Только в 1870 г., после сокрушительного разгрома французской армии прусской армией, противники Милютина приумолкли. В Пруссии давно была введена всеобщая воинская повинность, армия хорошо обучалась и была хорошо вооружена. В ноябре 1870 г. Милютин подает государю еще одну записку «О главных основаниях личной воинской повинности». Создаются две комиссии, на заседаниях которых подробно и детально, с приглашением военных специалистов и гражданских, разрабатываются положения о призыве. В конечном счете царь принял сторону реформатора.
1 января 1874 г. закон о воинской повинности был утвержден Александром II. По новому закону воинской повинности подлежали все лица мужского пола в возрасте 21–40 лет, подчеркивалось, что «защита Отечества составляет священную обязанность каждого русского гражданина». Все лица, достигшие 20 лет, тянули жребий. Те, кто вытянул номер, поступали в воинскую службу, а иные навсегда от нее освобождались, но до 40 лет зачислялись в государственное ополчение. Например, в 1874 г. из 725 тысяч человек, подлежащих призыву, было призвано 150 тысяч человек, в 1880 г. – из 809 тысяч – 212 тысяч человек. Общий срок действительной службы был установлен 6 лет в армии и 7 лет на флоте, в 1876 г. срок был сокращен до 5 лет. Для призывников с начальным образованием срок службы сокращался до 4 лет, со средним образованием – 1,5 г., с высшим образованием – 6 месяцев. Не призывались единственные сыновья и единственные кормильцы семьи.
Заметно улучшилась подготовка солдат, обучение стрельбе и саперному делу, физическая подготовка солдат. Солдат обучали грамоте. Более сложными, приближенными к боевым условиям стали военные учения. Была перестроена система военно-учебных заведений, перешедшая под общее руководство военного министра. Производство в офицерский чин теперь могло осуществляться только после окончания юнкерского училища или сдачи установленных экзаменов. С 1876 г. в военные учебные заведения стали принимать лиц всех сословий. 12 кадетских корпусов были заменены военными гимназиями, их программа была расширена за счет общеобразовательных предметов.
Армия заметно обновилась, она стала моложе, грамотнее, лучше подготовленной и лучше управляемой.