На фоне этих разочарований Алексеева все больше интересовали возможности хорошо знакомых ему представителей либеральной оппозиции. Главенствующие роли в ней занимали представители думского Прогрессивного блока и тесно связанные с ними руководители Военно-промышленного комитета (ВПК) и Союза земств и городов (Земгора). Глава ВПК А.И. Гучков был отлично знаком Алексееву еще с 1907 года, а лидеры Земгора князь Г Е. Львов и М.В. Челноков специально приезжали к нему в Ставку в январе 1916-го. Именно в либеральных кругах в течение второй половины этого года постепенно вызрела идея государственного переворота — а точнее, устранения правящего монарха и провозглашения императором цесаревича Алексея при регентстве великого князя Михаила Александровича. Начиная с февраля Гучков обратился к Алексееву с целым рядом писем, в которых прямо обвинял правительство в измене и взывал к генералу: «Мы в тылу бессильны или почти бессильны бороться с этим злом… Можете ли вы что-нибудь сделать? Не знаю. Но будьте уверены, что наша отвратительная политика (включая и нашу отвратительную дипломатию) грозит пересечь линии вашей хорошей стратегии в настоящем и окончательно исказить ее плоды в будущем». Тон этих писем явно говорил о том, что Гучков видел в Алексееве своего единомышленника…

Интересно, что узнавшая об этих письмах императрица Александра Федоровна сообщала мужу 18 сентября 1916 года: «Теперь идет переписка между Алексеевым и этой скотиной Гучковым, и он начинит его всякими мерзостями — предостереги его, это такая умная скотина, а Алексеев, без сомнения, станет прислушиваться к тому, что он говорит». В ответном письме император удивляется: «Откуда ты знаешь, что Гучков переписывается с Алексеевым? Я никогда раньше не слыхал об этом». Пригласив к себе Алексеева, Николай II поинтересовался, переписывается ли он с Гучковым, и получил отрицательный ответ. Впрочем, Гучков вскоре сам обнародовал свое письмо Алексееву от 15 августа — видимо, затем, чтобы «сжечь мосты» за Алексеевым и подтолкнуть его к более решительным действиям. Да и императрица снабдила мужа копией письма Гучкова к Алексееву.

К этому времени отношение Михаила Васильевича к правящему монарху успело кардинально измениться. На смену добродушной фразе «С ним мы спелись» постепенно начало приходить понимание того, что человек, находящийся во главе России, не может руководить гигантской страной, ведущей страшную войну. Мало-помалу Алексеев стал воспринимать Верховного главнокомандующего чуть ли не как помеху в своей работе. М.К. Лемке, наблюдавший М.В. Алексеева в Ставке, свидетельствовал: «Царь немало мешает ему в разработке стратегической стороны войны и внутренней организации армии, но кое-что М.В. удается отстоять от “вечного полковника”… Многое Алексеев делает и явочным порядком, т. е. докладывает царю уже о свершившемся факте, и поневоле получает одобрение — иногда с гримасой, иногда без нее. Иное дело личный состав: здесь царь имеет свои определенные мнения, симпатии и антипатии и сплошь и рядом решительно напоминает, что назначениями хочет ведать сам. Разумеется, такое вмешательство в значительной мере мешает и меняет все дело, всю мысль, а результаты получаются плачевные.