В ночь на 20 мая поезд ВВИ отправился в Саратов, потом, через несколько суток, в Сызрань, оттуда — в Самару. Н. И. Подвойский намеревался выехать далее в Оренбург, но в Самаре стало известно о начале мятежа чехословацкого корпуса. Этот корпус насчитывал около 45 тысяч человек и был сформирован из пленных чехов и словаков еще осенью 1917 года. Впоследствии по договоренности со странами Антанты он был объявлен частью французской армии и должен был быть переброшен через Владивосток из России во Францию при условии его лояльности к Советской власти и сдачи значительной части своего оружия. Но командование корпуса не спешило сдавать оружие. Кроме того, оно открыто поддерживало российскую контрреволюцию. К концу мая войска корпуса растянулись по всей Сибирской же-железнодорожной магистрали — от Пензы до Владивостока. Реакционному командованию с помощью стран Антанты удалось поднять корпус на мятеж против Советской власти. Контрреволюционные силы Поволжья, Урала, Сибири, Дальнего Востока поддержали мятежников.
Н. И. Подвойский сразу оценил масштабы происшедшего. Он принял решение срочно выехать всему составу ВВИ навстречу надвигающейся опасности, в район Уфы, где провести экстренную работу по формированию частей Красной Армии, чтобы прикрыть промышленный Южный Урал. Оп дал телеграмму в Москву, в которой сообщил об изменении планов ВВИ и, не дожидаясь ответа, выехал в Уфу.
Заранее предупрежденные железнодорожники почти беспрепятственно пропускали поезд ВВИ. Николай Ильич часами сидел над картами, прикидывал возможные направления наступления мятежников. Было совершенно ясно, что первыми объектами их захвата будут Поволжье и Урал. Впоследствии так оно и оказалось — белочехи повернули на запад, якобы для создания антигерманского фронта с востока, и на Урал.
29 мая поезд ВВИ прибыл в Уфу. Один из ведущих местных военных работников, член партии большевиков с 1901 года, боевик времен первой русской революции Э. С. Кадомцев сообщил Н. И. Подвойскому, что военных сил в губернии много — около 20 тысяч бойцов. Но из-за сильного влияния левых эсеров они существуют не в форме отрядов, а как в 1905 году — в форме дружин, то есть крепко привязаны к месту работы и жительства. Левоэсеровская линия выражается в их лозунгах: «Долой дисциплину!», «Долой запертую в казармы армию!», «Долой назначаемые командные кадры!»
— Преодолеть влияние левых эсеров в военном строительстве нам еще не удалось, — сказал Э. С. Кадомцев. — Но теперь, в связи с мятежом чехословаков, надо попытаться его сломить. Думаю, что поможет и ваш авторитет как представителя Центра.
В тот же день на экстренно созванном заседании исполкома губсовета Н. И. Подвойскому удалось добиться принятия резолюции о создании военкоматов и немедленном начале формирования частей регулярной Красной Армии. После трехдневной борьбы местных большевиков, сплоченных Н. И. Подвойским, за такую же резолюцию проголосовал III губернский съезд Советов, проходивший 3–5 июня.
Между тем 29 мая в Москве ВЦИК под председательством Я. М. Свердлова принял постановление о переходе к комплектованию Красной Армии на основе воинской повинности. Но принудительный набор предписывалось провести сначала в наиболее угрожаемых областях и в рабочих центрах, и обязательно с разрешения Наркомвоена. Эта весть дошла до Уфы не сразу, и Николай Ильич вынужден был решать проблемы экстренного формирования военных сил самостоятельно, опираясь на собственный разум и полномочия, данные ему Центром.
Белочехи и казаки захватывали один город за другим. Пока Н. И. Подвойский был занят на губернском съезде Советов, член ВВИ Р. И. Берзин по его заданию проанализировал ход боевых действий и доложил, что неудачи во многом объясняются тем, что нет единого командования, не налажено снабжение, слаба дисциплина. Каждый отряд имеет своего командующего, указывал Берзин, свой штаб, и никто не хочет никому подчиняться, отряды ведут «эшелонную войну», не желая никуда отходить от железных дорог. Выводы Р. И. Берзина совпали с впечатлениями Николая Ильича от поездки на передовую, которую он осуществил на второй день после приезда в Уфу. Наспех сколоченные, необученные, управляемые малоподготовленными людьми красноармейские отряды, несмотря на мужество и преданность, отступали. Попытки Н. И. Подвойского задержать их отступление под Златоустом не дали успеха — для этого не было даже самого маленького резерва.
Нужны были срочные, кардинальные меры. 30 мая Н. И Подвойский издал приказ, в котором объявил, что «нашел необходимым принять на себя временно общее руководство до сих пор разрозненными оперативными действиями против мятежных чехословацких эшелонов, впредь до сформирования полевых штабов». Он взвалил на свои плечи функции командующего фронтом, а на Высшую Военную Инспекцию — функции штаба фронта. В той обстановке это было наиболее целесообразно.