В июне 1894 года Алексеев получил перевод по службе в канцелярию Военно-учетного комитета Главного штаба, где сначала был младшим делопроизводителем, а затем старшим. Там он был произведен в подполковники (30 августа 1894 года) и полковники (5 апреля 1898 года этот чин дал офицеру права потомственного дворянства). С этого времени служба Алексеева была связана со штабной работой, если не считать цензового командования батальоном в лейб-гвардии Гренадерском полку (1900) и командования бригадой 22-й пехотной дивизии (1907).
Одновременно со службой в Главном штабе Алексеев преподавал на кафедре русского военного искусства Николаевской академии Генерального штаба, последовательно занимая должности экстраординарного (1898—1901), ординарного (1901—1904) и заслуженного ординарного (с 1904) профессоров. Об Алексееве-преподавателе один из его учеников, ставший впоследствии генерал-лейтенантом, А.П. Богаевский, вспоминал так: «Он остался таким же кропотливым и усердным работником, прекрасно излагавшим свой далеко не легкий предмет. Он не был выдающимся талантом в этом отношении, но то, что нужно нам было знать, он давал в строго научной форме и сжатом образном изложении. Мы знали, что все, что он говорит, — не фантазия, а действительно так и было, потому что каждый исторический факт он изучал и проверял по массе источников».
На протяжении трех лет, с августа 1900-го по май 1903 года, Генерального штаба полковник Алексеев был начальником оперативного отделения только что созданной генерал-квартирмейстерской части Главного штаба, а затем занял должность начальника отдела Главного штаба. 28 марта 1904 года последовало производство в чин генерал-майора. Михаилу Васильевичу было в то время всего 46 лет.
Именно в это время окончательно сформировались присущий Алексееву стиль штабной работы и его характер. Сослуживцы характеризовали его так: «Алексеев — человек рабочий, сурово воспитанный трудовой жизнью бедняка, мягкий по внешнему выражению своих чувств, но твердый в основании своих корней; веселье и юмор свойственны ему скорее как сатирику; человек, не умеющий сказать слова с людьми, с которыми по существу не о чем или незачем говорить, военный по всему своему складу, природный воин, одаренный всем, что нужно руководителю, кроме разве умения быть иногда жестоким; человек, которого нельзя себе представить ни в какой другой обстановке, практик военного дела, которое знает от юнкерского ранца до руководства крупными строевыми частями; очень доступный каждому, лишенный всякой внешней помпы, товарищ всех подчиненных, не способный к интригам». Всех поражала память Алексеева: после нескольких часов изучения карт он был способен составить подробную директиву, где на память, не сверяясь с документами, обозначал расстановку на фронте каждого корпуса, дивизии и полка.
Заслуги Алексеева в мирное время были отмечены орденами Святого Станислава 2-й степени (1892), Святой Анны 2-й степени (1896), Святого Владимира 4-й степени с бантом за 25 лет службы (1900) и Святого Владимира 3-й степени (1901).
С началом Русско-японской войны М.В. Алексеев 30 октября 1904 года был по собственному желанию назначен генерал-квартирмейстером 3-й Маньчжурской армии, которой командовал генерал от кавалерии барон А.В. Каульбарс.
Фронтовыми впечатлениями Алексеев откровенно делился с женой в письмах. Они содержат и невеселые размышления об увиденном. «Вообще наши начальники мало образованы в своем специальном военном деле и совершенно не подготовлены к управлению большими силами, — констатировал Алексеев. — Наши большие силы парализуются бесконечным исканием плана и в то же время отсутствием ясной, простой идеи, что нужно. Нет идеи, нет и решительности. Колебания и боязнь — вот наши недуги и болезни, мы не хотим рисковать ничем и бьем лоб об укрепленные деревни. Мелкие цели, крупные потери, топтание на месте, противник остается хозяином положения, а быть хозяевами должны были бы и могли бы быть мы… Отсюда вытекают те боязливые задачи, узкие по содержанию, которые ставит себе Главнокомандующий, то мотание войск, которое совершается при первой вести о появлении там или там противника. Полководцу нужны: талант, счастье, решимость. Не говорю про знание, без которого нельзя браться за дело. Военного счастья нет, а решимость просто отсутствует, а между тем на войне нужно дерзать и нельзя все рассчитывать. Стремление к последнему ведет за собою то, что мы никак не выберемся из области взятия той или другой деревни, вместо постановки цели ясной, широкой, определенной и направления для этого сил достаточных. Мы уже богаты и при умении и смелости могли бы многое сделать». Подводя итоги увиденного, генерал заключал: «Будем просить Бога — да смилуется над нашей Родиной и просветит ум и дух того, в чьих руках и военная слава, и судьба государства; пониже — в конце концов не сдадут, а на своих плечах вынесут свое дело».
Не раз в ходе боевых действий М.В. Алексееву приходилось делать рекогносцировки под огнем противника. За проявленное мужество генерал-майор 23 ноября 1905 года был удостоен ордена Святого Станислава 1-й степени с мечами, а 23 апреля 1906 года — Золотого оружия с надписью «За храбрость». В том же году он был награжден и своей второй «звездой» — орденом Святой Анны 1-й степени.
27 сентября 1906 года генерал-майор Алексеев получил назначение на должность 1-го обер-квартирмейстера Главного управления Генерального штаба (ГУГШ). Он стал ближайшим помощником начальника ГУГШ генерала от инфантерии Ф.Ф. Палицына и, по мнению военного историка и теоретика Н.Н. Головина, «обладая громадным опытом стратегической работы и в то же время ученым стажем, представлял собою наиболее квалифицированного работника Большого Генерального штаба». На ГУГШ в то время была возложена серьезная обязанность — проанализировать ход Русско-японской войны, обобщить и учесть ее опыт в ходе планирования предстоящих кампаний.
Сослуживец и друг Алексеева генерал-лейтенант В.Е. Борисов вспоминал: «В 1907 году я встретился с Алексеевым в Главном Управлении Генерального Штаба. В это время осуществилось давнишнее стремление нашего Генерального Штаба выделиться из тяжелого плена в объятиях военно-административного Главного Штаба и отдаться всецело стратегической подготовке к будущей войне. Это удалось только после ряда поражений, испытанных нашей армией во время Японской войны. Первым нашим, независимым от военного министра, начальником Генерального Штаба был генерал Ф.Ф. Палицын. Алексеев был 1-м обер-квартирмейстером, я был 2-м. Алексеев ведал общим планом будущей войны. Я ведал развертыванием сил на западном фронте от Швеции до Румынии. Генерал Скерский был 3-м обер-квартирмейстером и ведал Кавказом и всей Азиатской Россией. Алексеев, несмотря на равное со мной и Скерским служебное положение, заменял для нас генерал-квартирмейстера (вместо бывшего им больного генерала Дубасова), так как Алексеев, состоявший до этого назначения Начальником оперативного отделения Главного Штаба, а во время Русско-Японской войны Генерал-Квартирмейстером Штаба 3-ей армии, знал ход всего стратегического делопроизводства и историю всех стратегических, организационных и военно-административных начинаний».
