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