Теперь перед чешским командованием вставала задача всеми правдами и неправдами добыть за эти дни подвижной состав. «Врагами» на этот раз оказались не немцы, а красные командиры всех уровней, которые, разумеется, мечтали, чтобы чехи и дальше проливали свою кровь, прикрывая беспорядочное бегство их отрядов. И с новой задачей чешским командирам вполне удалось справиться, причём особенным хладнокровием и дипломатическими способностями отличился недавно присоединившийся к корпусу Генерального Штаба подполковник Б. Ф. Ушаков, вскоре получивший должность начальника Штаба 2-й Чешско-Словацкой дивизии.
Вечером 13 марта последние чешские части погрузились в вагоны, и их эшелоны под видом составов с ранеными немедленно двинулись в сторону Курска. Антонов-Овсеенко рвал и метал, обвиняя чехов в предательстве, но поделать ничего не мог. Гайда не принимал участия в этих боях, вплоть до марта 1918 года он был прикомандирован к штабу 2-й дивизии, оставаясь фактически без должности.
После того, как эшелоны пересекли границу Украины с РСФСР, руководство Отделения ЧСНС в России немедленно обратилось к Совету Народных Комиссаров с просьбой разрешить частям корпуса проезд во Францию. Для переговоров Совнарком делегировал И. В. Сталина. После долгих дебатов 27 марта было заключено соглашение, по которому частям корпуса был разрешён проезд во Владивосток. При этом изначальным требованием большевиков являлось полное разоружение и роспуск корпуса, но от этого им пока что пришлось отказаться. Однако и делегаты «От- бочки» пошли на серьёзные уступки: они согласились с формулировкой, что «чехословаки продвигаются не как боевая единица, а как группа свободных граждан, везущих с собой известное количество оружия для защиты от покушений со стороны контрреволюционеров». Соответственно корпус должен был разоружиться, оставив только по 100 винтовок и 1 пулемёту на эшелон (примерно на 1 000 человек).
Эти условия вызвали резкое недовольство в рядах легионеров. Часть офицеров пыталась протестовать. Тогда большевики потребовали изгнать «представителей реакционного командного состава», на что члены «Отбочки» с лёгкостью согласились. В результате среди русских офицеров корпуса была проведена жёсткая чистка. Многие вынуждены были уйти, а большинство оставшихся, ощущая шаткость своего положения, предпочитало сохранять сугубую лояльность политическому руководству во всех случаях, порой - вопреки здравому смыслу. Исход русских офицеров обернулся личной удачей для Гайды, 28 марта 1918 года он принял командование 7-м Чешско-Словацким Татранским стрелковым полком после ухода прежнего командира полка полковника Смуглова.
Итак, чехам пришлось подчиниться условиям соглашения. Всё тяжёлое оружие, боеприпасы и запасы снаряжения были сданы. Винтовки и пулемёты полки сдавали по мере проезда эшелонов через Пензу, и только после этого корпусу, насчитывавшему в своём составе 35 300 человек, в 63 эшелонах было разрешено ехать далее в Сибирь. Чехи расставались с оружием очень неохотно, что, учитывая полное бесправие, воцарившееся в стране, было вполне понятно. Многие эшелоны утаивали часть винтовок сверх положенного лимита, но в любом случае - подавляющее большинство людей в эшелонах ехали безоружными. К маю первые двенадцать эшелонов уже прибыли во Владивосток, но все остальные растянулись на огромном пространстве в 7 000 км от Ртищева (под Пензой) до Иркутска. Не подлежит сомнению, что на тот момент чехословаки, причём как руководство корпуса, так и простые легионеры, хотели только одного: как можно скорее покинуть сошедшую с ума Россию и перебраться во Францию, где в боях завершавшейся мировой войны завоевать для своей родины право на независимость.
Однако движение их поездов по Сибири всё замедлялось и; наконец, к маю практически совсем остановилось. И одновременно Совет Народных Комиссаров предложил Отделению ЧСНС в России отправить все эшелоны вместо Владивостока северным путём через Архангельск и Мурманск.
Растерявшаяся «Отбочка» не нашла ничего лучше, как выслать 9 мая в Москву делегатов, чтобы добиться согласия Советского правительства отправить через Владивосток хотя бы те поезда, которые к этому времени находились уже восточнее Омска, а северным путём - те, что стояли западнее Омска. При этом мнения простых чешских легионеров никто не спрашивал. А они сами отнеслись к этому новому проекту резко отрицательно. Чехи не доверяли Советской власти и видели в этих непрекращающихся нарушениях достигнутых соглашений одну только цель - уничтожить корпус как единое целое, а затем всех его бойцов поодиночке выдать на расправу немцам. Более того, рядовые бойцы не доверяли уже и своим политическим представителям, шедшим на всё новые и новые уступки, причём за их счёт. Одновременно ухудшались отношения и с Советами на местах: все они в больших городах по Транссибирской железной дороге требовали от чешских эшелонов только одного - вопреки всем прежним договорённостям полностью сдать оружие.