Противником Гайды в этих боях являлись вооружённые силы «Центросибири» - Центрального Исполнительного Комитета Советов Сибири. Центросибирь была создана ещё в конце 1917 года и претендовала на координацию деятельности всех Советов Западной и Восточной Сибири, а также Дальневосточного края, хотя фактически её власть распространялась лишь на территорию Восточной Сибири от Красноярска до Читы. Теперь, оказавшись отрезанными от Москвы, представители Центросибири запросили у Гайды перемирия, с тем чтобы связаться со столицей и попытаться разрешить конфликт мирным путём. Гайда совершенно не верил в такую возможность, однако перемирие было ему выгодно с тактической точки зрения, и оно было заключено до 16 июня, причём распространялось и на отряд Ушакова в Канске. Теперь, обезопасив себя на время с востока, Гайда мог нанести следующий удар уже на запад, в сторону Омска. 15 июня пал Барнаул, а следом за ним были заняты Бийск и Семипалатинск.
Помощь подходила и с запада, со стороны Челябинской группы. Решающий бой здесь произошёл 7 июня на станции Марьянов- ка: омские красногвардейцы были в нём наголову разбиты, и в тот же день Омск был освобождён с помощью выступившей местной подпольной организации. Вскоре в Омске было сформировано Временное Сибирское Правительство, и этот город окончательно превратился в столицу Белой Сибири. 8 июня на станции Татарская произошло соединение частей Гайды с западным отрядом поручика Сырового. Таким образом, путь до Челябинска был открыт, и Гайда вновь мог заняться восточным направлением.
Тем временем 12 июня из войск Временного Сибирского Правительства было образовано два корпуса: 1-й Средне-Сибирский, под командой подполковника А. Н. Пепеляева, и 2-й Степной Сибирский, под командой полковника П. П. Иванова-Ринова. Средне-Сибирский корпус должен был наступать на восток, совместно с группой Гайды. Его составили добровольческие отряды из Средней Сибири: Томск дал четыре полка, Ново-Николаевск - два, Барнаул и Красноярск по одному. Эти полки насчитывали пока не более чем по 300-400 штыков при нескольких пулемётах, во всём корпусе было всего 8 орудий, но части были сформированы исключительно из добровольцев, и их боевой дух был очень высок. В свою очередь, и Гайда для пополнения своих частей 21 июня объявил по всем лагерям военнопленных на освобождённой территории мобилизацию чехов и словаков.
Перемирие с Центросибирью заканчивалось вечером 15 июня. На следующий же день у Мариинска разгорелся ожесточённый бой. Гайда нанёс удар с фронта и тыла, причём лично возглавил обходную колонну, и красные в панике бежали к Красноярску. Одновременно 16 июня Ушаков наступал на станцию Клюквенная, и это решило судьбу Красноярска. 19-го в городе произошло восстание, местный Совет поспешно бежал на пароходах по Енисею, а на следующий день в город уже вступала с востока ударная рота из отряда Ушакова, а с запада - самодельный бронепоезд Гайды. После соединения отрядов подполковник Ушаков принял должность начальника Штаба в объединённом отряде Гайды. Своими знаниями, энергией и блестящим талантом тактика Ушаков чрезвычайно способствовал всем дальнейшим успехам «Восточного отряда Чехо-войск» вплоть до своей трагической гибели. Гайда очень уважал и любил его.
Между тем войска Центросибири со стороны Иркутска, сосредоточив 5 000 человек, нанесли удар по Нижнеудинску, но в упорном трёхдневном бою 24-26 июня эта группировка была наголову разбита. Красные бежали столь стремительно, что преследование их замедлялось лишь постоянной необходимостью чинить повреждённое полотно железной дороги и взорванные мосты. Центросибирь поспешно переехала в Верхнеудинск, за ней последовали и деморализованные красные отряды. 11 июля войска группы Гайды освободили Иркутск. Там 1-й Средне-Сибирский корпус Пепеляева был разделён на две дивизии, а все русские и чешские войска, оперирующие в этом районе, объединены в Восточный фронт, который возглавил произведённый в полковники Гайда.
Однако борьба ещё далеко не была закончена. Необходимо было как можно скорее, не останавливаясь, захватить тоннели на Круго-Байкальской магистрали и предотвратить подрыв их большевиками. Первые 38 тоннелей удалось спасти, и всё же около 5 часов вечера 19 июля, когда чехо-русские отряды, развивая успех, занимали станцию Слюдянка, невдалеке прогремел мощный взрыв: красные взорвали восточный выход из последнего тоннеля - № 39. Это задержало дальнейшее наступление почти на две недели; лишь 31 июля там можно было начать ремонтные работы. Красные между тем получили уникальную возможность собраться с силами и самим перейти в контрнаступление.