Училище было закончено по 1-му разряду, в чине прапорщика 1 декабря 1876 года. Это было весьма неплохим началом военной карьеры. Российская армия в это время переживала период перемен и реорганизаций. Вводились новые уставы, осваивались новые виды вооружения, повышалась профессиональная подготовка солдат и офицеров. Прежний, «кастовый» характер отношений в военной среде навсегда уходил в прошлое.
После неудачной Крымской войны угроза новых конфликтов не исчезала. В 1877 г. начинается война с Османской империей. И в «турецкий поход» офицер, произведенный в чин прапорщика, вышел в рядах своего родного 64-го пехотного Казанского Его Императорского Высочества Великого князя Михаила Николаевича полка. Полк выступил из Витебска к южным рубежам в апреле 1877 года.
Полученное на Балканах «боевое крещение» не могло не отразиться на мировоззрении Алексеева. Ведь это была «Освободительная война» братских славянских народов против «османского ига». Патриотический подъем, охвативший войска, идущие в бой за «свободу славянства», убеждал в необходимости укрепления военного авторитета России. В августе—сентябре 1877 г. Казанский полк участвовал в тяжелых боях под Плевной. Алексеев служил в должности полкового адъютанта в штабе отряда генерала от инфантерии Михаила Дмитриевича Скобелева. Начальники Алексеева и сам легендарный «белый генерал» неоднократно отмечали исполнительность и смелость своего адъютанта. Боевые ордена Святого Станислава 3-й степени с мечами и бантом (за бои на Шипкинском перевале), Святой Анны 3-й степени с мечами и бантом (1879 г.), Святой Анны 4-й степени («аннинский темляк на шашку») и румынский Военный крест (1878 г.) стали его отличиями, а полученное ранение в палец Алексеев называл «пустяковым» и даже не вспоминал об этом. Офицеры штаба Скобелева доставляли донесения и составляли планы атак не в тыловой «тиши», а на передовой линии огня, и молодой адъютант неоднократно отличался среди них. На передовой, под сенью именного «скобелевского значка», проявлялись такие качества его характера, как смелость в решении поставленных задач и четкость в исполнении штабных предписаний.
Участие в боевых действиях способствовало и продвижению по службе. Начав войну 19-летним прапорщиком, Михаил Алексеев к концу военных действий дослужился до чина подпоручика (31 октября 1878 г.). 25 января 1881 г. был произведен в поручики, а 15 мая 1883 г. — «за отличия по службе» — в штабс-капитаны.
Примечательные подробности участия Казанского полка в Русско-турецкой войне содержит его «полковая история»: изданная в Санкт-Петербурге в 1888 г. книга «Походы 64-го пехотного Казанского Его Императорского Высочества Великого князя Михаила Николаевича полка. 1642—1700—1888» представляет не только значительный исторический интерес, но и имеет непосредственное отношение к биографии Михаила Васильевича. В предисловии указывалось, что сведения «о походах и делах полка в войну 1877—1878 годов» получены «на основании рукописи» штабс-капитана М.В. Алексеева. Добрая треть «полковой истории» отражала первый военно-научный и литературный опыт будущего Верховного Главнокомандующего.