Профессор Императорской Военной академии по кафедре военной географии (3.01.1845), а затем военной статистики. Прикомандирован к штабу Военно-учебных заведений для управления 3-м (воспитательным) отделением. Полковник (21.4.1847).
Назначен для особых поручений к военному министру (26.10.1848). Утвержден членом Ученого комитета Главного управления путей сообщения и публичных зданий (19.12.1848). Сопровождал императора Николая I за границу в Олмюц и Потсдам во время дипломатических переговоров с австрийским императором Францем-Иосифом и прусским королем Фридрихом-Вильгельмом IV (9.1853).
Избран членом-корреспондентом Академии наук (29.12.1853). Член комиссии для описания губерний Киевского Учебного округа (30.3.1854). Генерал-майор (11.04.1854). Назначен производителем дел Балтийского комитета (8.1855). Член комиссии «для улучшений по военной части» (2.1856), в которую представил записку о коренной реорганизации армии.
Начальник Главного штаба Кавказской армии (15.10.1856—59). Генерал-лейтенант (30.08.1858). Участник реформы государственного и военного управления на Кавказе, в том числе ведено пятнадцать военно-административных округов, привлечена к власти местная аристократия, сформирована местная милиция, реорганизованы и перевооружены войска, начато строительство коммуникаций, в том числе дороги через Главный Кавказский хребет. Разработчик плана штурма резиденции Шамиля аула Ведень (1858), находился при войсках Чеченского отряда, участвовал в овладении укрепленным аулом Гунибом, где был взят в плен Шамиль (7—8.1859). Генерал-адъютант (6.08.1859). Избран почетным членом Императорского Харьковского университета (12.04.1860).
Товарищ (заместитель) военного министра (30.08.1860). Избран почетным членом Медико-Хирургической академии (23.03.1861).
Военный министр (9.11.1861). Генерал от инфантерии (27.03.1866). За два месяца подготовил проект реформ и доложил его Александру II (15.01.1862). Провёл ряд военных реформ с целью превращения русской армии в современную массовую армию (1860—1870). По предложению Милютина была введена закрепленная в Положении 1867 г. стройная система военного управления. Вместо многочисленных департаментов создавались главные управления, ведавшие целиком той или иной отраслью. Аппарат Военного министерства сократился почти на тысячу человек, а канцелярская переписка – наполовину. Вся территория империи была разделена на 15 военных округов (Положение 6.8.1864), которым были переданы все функции военного управления на местах. В случае войны управления округов преобразовывались в штабы объединений. Предложено привлекать к воинской повинности привилегированные слои общества и ввести «отпуска» после седьмого-восьмого года службы. Эти меры позволили увеличить запас военнообязанных более чем в два раза (1862 г. – 210 тысяч, 1870 – 553 тысячи).