Но время требовало совсем другого. В 1840 году, с целью повышения престижности академии, было принято решение о комплектовании службы Генерального штаба преимущественно ее выпускниками. Сразу же следует отметить, что, состоя в службе Генерального штаба, офицер в то время мог служить не только в столице, но и в войсках. К службе Генерального штаба относили некоторые штабные должности, начиная с начальника штаба отдельного полка (бригады) и обер-квартирмейстера (начальника оперативного отделения) штаба дивизии. Следовательно, причисление к Генеральному штабу не избавляло офицера от службы где-нибудь в захолустье, на самых дальних окраинах Российской империи.
Крымская война (1853–1856 гг.) в очередной раз показала низкую грамотность основной массы командно-штабного состава русских войск. На этом фоне выпускники Императорской военной академии выглядели намного лучше. Им поручали сложные расчеты при подготовке боевых действий и при передвижениях войск перед боем, доверяли контроль за сложным маневром, использовали в качестве доверенных советников при оценке обстановки, выработке решения и в процессе его реализации.
Приход к власти в стране и годы правления нового императора Александра II были ознаменованы многими положительными переменами в жизни российского общества. На политический олимп взошли новые люди, принеся с собой новые идеи.
В 1861 году военным министром был назначен А. Д. Милютин, выпускник Императорской военной академии 1836 года, который затем с 1845 по 1856 год работал в этом военно-учебном заведении в должности профессора военной статистики. Возглавив военное министерство, Алексей Дмитриевич развернул активную деятельность по разработке и осуществлению военных реформ в России. Одним из ведущих направлений этих реформ были мероприятия по улучшению подготовки командных и штабных кадров, в том числе и в Николаевской академии Генерального штаба (переименована после смерти Николая I).
А. Д. Милютин и его помощники пришли к заключению, что грамотная штабная работа в боевой обстановке нередко ценится выше волевого решения командира. Особенно это касалось штабов высшего войскового звена (дивизия, корпус, действующая армия), где приходилось планировать и управлять действиями разнородных сил, разбросанных на большом пространстве. В этих условиях командир (командующий) лишался возможности зрительно наблюдать за всем полем боя, наступало время выработки решения по топографическим картам с помощью математических расчетов, а управления подчиненными войсками посредством передачи письменных приказов.
Крымская война (1853–1856 гг.) показала недостаток в войсках грамотных офицеров, особенно среди командиров (командующих) высшего звена управления. А. Д. Милютин предложил выпускников академии назначать не только на штабные, но и на командные должности. Изменилось и отношение к военной науке, важнейшим центром которой в то время была Николаевская академия Генерального штаба. В ее стенах от простого изучения уже прошедших войн перешли к анализу отдельных операций и боев, были сделаны первые попытки научного прогнозирования войн будущего.
Создавалась отечественная научная база. С конца 50-х до первой половины 70-х годов профессорско-преподавательским составом и выпускниками академии было разработано и издано большое количество научных трудов. Особую ценность представляли научные труды профессоров В. М. Аничкова, М. И. Богдановича, Г. А. Леера, А. А. Непокойчицкого, М. И. Драгомирова, Н. В. Левицкого, Н. Н. Обручева, И. М. Зайцева, А. И. Макшеева, А. Е. Станкевича и других.
В ноябре 1862 года начальником академии был назначен генерал-майор А. Н. Леонтьев. Новый начальник не имел особых военных заслуг, но отличался большой работоспособностью, выдержкой и тактом. Он пользовался большим уважением в столичных военных кругах. Благодаря этому А. Н. Леонтьеву и его помощникам для академии удалось сделать многое. В частности, был улучшен подбор абитуриентов и созданы условия для их подготовки к вступительным экзаменам. Леонтьев добился того, что начиная с 1863 года в академию могли поступать только офицеры, прослужившие в войсках не менее четырех лет. При этом время пребывания в отпусках, прохождения службы в должности личных адъютантов и в других нестроевых должностях в срок строевой выслуги не входило. Зато преимущество отдавалось офицерам, имевшим боевой опыт и награжденным орденами.
М. Д. Скобелев и рассчитывал на это обстоятельство, когда по инстанции подавал рапорт о своем желании поступить в Николаевскую академию Генерального штаба в 1866 году. Рассматривался этот рапорт несколькими начальниками, и при отборе учитывались самые различные факторы. Но рапорт Скобелева ни у кого из них не вызвал возражений – сыграли свою роль «генеральская» фамилия и орден, полученный за бои в Польше.