Военные реформы проводилось поэтапно в течение целого десятилетия. По «Положению» 1864 года территория России была разделена на пятнадцать военных округов. Управления округа (артиллерийское, инженерное, интендантское, военно-медицинское) имели двойное подчинение – командующему войсками и соответствующим главным управлениям Военного министерства. По инициативе Милютина старое деление войск на корпуса упразднили, и высшей тактической единицей стала дивизия, однако через несколько лет корпуса восстановили. Военно-окружная реформа обеспечила оперативное руководство войсками с целью их быстрой мобилизации. В итоге реформы 1867 года была создана стройная система центрального военного управления, упразднены дублирующие структуры, аппарат министерства сократился почти на тысячу человек, вдвое уменьшилась канцелярская переписка. В 1868 году император утвердил «Положение о полевом управлении войск в военное время», которое уточняло функции главнокомандующего и его штаба, координацию их действий с окружными управлениями. Однако это нововведение страдало серьезными недостатками и на практике привело к излишней бюрократизации военного управления. «Положение» 1868 года считается специалистами наименее удачной реформой Милютина.
Приоритетное внимание министерство уделяло подготовке офицерских кадров. В середине 1860-х годов была проведена реформа системы военного образования. Милютин считал раннюю военную специализацию вредной для формирования личности молодого человека. В кадетских корпусах традиции лихого удальства и корпоративный дух сочетались с рутинностью преподавания, профессиональной некомпетентностью и солдафонством. Министр упразднил кадетские корпуса и учредил военные гимназии – средние учебные заведения с программой близкой к курсу реальной гимназии. Таким образом предполагалось повысить общеобразовательный уровень будущих офицеров. Кроме того, на основе специальных классов бывших кадетских корпусов создавались военные училища, куда принимались лица, получившие среднее образование. В итоге значительно повысилось качество преподавания в военных гимназиях, улучшился контингент поступавших в военные училища. Офицерский корпус ежегодно стал пополняться более образованными и квалифицированными кадрами в количестве 600 человек. В ходе перестройки были созданы также юнкерские военные училища с двухгодичным сроком обучения. Для поступления в них требовались знания в объеме четырех классов среднего учебного заведения. Юнкерские училища ежегодно выпускали около полутора тысяч офицеров. Министерство проявляло заботу и о высшем военном образовании: в соответствии с новыми научными достижениями систематически пересматривались программы и учебные планы академий. Помимо уже существовавших трех академий (Генерального штаба, Артиллерийской и Инженерной) открылась Военно-юридическая академия.
Большая работа проводилась и с рядовым составом. Милютин, приверженный гуманистическим ценностям, действовал в соответствии с духом времени, апеллируя к личности солдата. Он стремился освободить низшие чины от изнурительной муштры, повысить уровень их обучения. В войсках была усовершенствована боевая, строевая и физическая подготовка, многое было сделано для распространения грамотности, регулярно стали выходить специальные издания «Солдатские беседы» и «Чтение для солдат», были организованы полковые и ротные библиотеки. Министерство значительно улучшило систему армейского здравоохранения, развернуло строительство казарм, увеличило размеры провиантского и фуражного довольствия, ввело более удобное обмундирование. Одновременно с принятием закона об отмене телесных наказаний 17 апреля 1863 года Милютину удалось добиться упразднения наиболее жестоких видов наказаний, применявшихся в армии (таких, как кошки, шпицрутены, плети, клеймение). Либеральная судебная реформа 1864 года позволила военному ведомству принять в 1867-м новый военно-судный устав, основанный на началах гласности и состязательности.