Алексеев был «причислен к Генеральному штабу и назначен на службу в Петербургский военный округ». Летом он начал службу в штабе округа, хотя и не испытывал удовлетворения от однообразия военно-бюрократической системы. Вскоре начались лагерные сборы при штабе Гвардейского корпуса, во время которых Алексеев «отдыхал душой», вернувшись к привычным для себя полевым занятиям. На маневрах, в «Высочайшем присутствии», Алексееву было поручено руководить высадкой «немецкого десанта» под Петербургом, тогда как прибывший на маневры император Германской империи Вильгельм II Гогенцоллерн должен был «защищать» российскую столицу.
Тем же летом, неожиданно, выпускнику Академии удалось не только получить дополнительный заработок, что при перспективе создания семьи было отнюдь не лишним, но и получить первый опыт профессиональной преподавательской работы. Ему предоставили возможность проведения занятий по топографическим съемкам и военно-административному праву у юнкеров Николаевского кавалерийского училища. И хотя первоначально он намеревался оценивать воспитанников «но всей строгости», ему быстро пришлось столкнуться с «неписаными правилами» поведения в этом элитном училище, готовившем офицеров кавалерийских полков. С присущей ему мягкостью и терпимым отношением к неуспевающим Алексеев немного завышал оценку. Вот как объяснял он это в одном из писем Ане Пироцкой: «Прошло кажется хорошо, затрудняюсь я, разве, в одном — сделать оценку баллами этих юношей. По справедливости — они особо многого не заслуживают, но по принятым обычаям в училище их оценивают более чем снисходительно. Вот нужно уловить эту меру снисходительности, к ней примериться. Ведь они сами не виноваты, что мало знают, мало умеют. С них мало требовали, и было бы несправедливо не принять это во внимание».
Первый педагогический опыт 1890—1891 учебного года оказался удачным. Юнкера «приняли» нового преподавателя. Во многом его занятия напоминали «беседы», проводившиеся в роте Казанского полка. Весьма примечательные «психологические» характеристики занятий капитана Алексеева приводил его ученик, будущий донской атаман генерал-лейтенант А.П. Богаевский (статья в журнале «Донская волна» в январе 1919 г.). «Четверть века тому назад, — вспоминал он, — юнкером Николаевского кавалерийского училища я впервые увидел подполковника Генерального штаба М.В. Алексеева. Он читал в моем классе лекции по администрации, науке нужной, но весьма скучной. Хороший тон и “традиции юнкеров славной школы” повелевали тогда относиться с уважением только к верховой езде и вообще к наукам, имевшим непосредственное к ней отношение…