Затем Гайда отправился во Владивосток. Имея мандат Челябинского съезда на руководство всеми чешскими войсками в Сибири, а также опираясь на соглашение о подчинении ему частей Сибирской Армии на Восточном фронте, он считал себя Главнокомандующим всеми чешскими и русскими войсками на Дальнем Востоке и, соответственно, рассматривал свою поездку как инспекционную. Но очень скоро ему пришлось убедиться, что это не так. Владивосток фактически находился под управлением представителей союзников, а кроме того, в нём обретались целых два русских «правительства»: П. Я. Дербера и генерала Д. Л. Хорвата, которые не столько управляли Приморьем (так как союзники не допускали этого), сколько боролись между собой, да к тому же оба не признавали власти Сибирского Правительства в Омске. Наибольшим весом обладали японцы, но им приходилось действовать с постоянной оглядкой на других союзников по Антанте.
И вот в эту атмосферу политических интриг новоиспечённый генерал Гайда ворвался с напором и грацией слона в посудной лавке. В течение нескольких дней он успел перессориться с японцами, Атаманом Семёновым, Хорватом и русским комендантом Владивостока полковником Бутенко. Вскоре японцы объявили, что для них Гайда как Главнокомандующий не существует, и во избежание международного конфликта чешское руководство поспешило отправить того обратно на фронт, назначив 26 сентября 1918 года начальником 2-й Чешско-Словацкой стрелковой дивизии, которая должна была как можно скорее сосредоточиться в районе Екатеринбурга. Во второй половине сентября полки дивизии двинулись по железной дороге на запад, а вскоре за ними последовал и Гайда. Напоследок он ещё раз успел «учудить», назначив своего заместителя полковника Кадлеца командующим всеми войсками на линии КВЖД и оставив в его распоряжении сильный чешский отряд. На этот раз обиженными оказались также местные китайские власти, а проживавший в это время в Харбине генерал барон А. П. Будберг занёс в свой дневник следующие ехидные замечания:
«27 сентября. Гайда умчался на запад, назначив полковника Кадлеца главнокомандующим в полосе отчуждения, то есть смешав этим и без того сумбурное здесь положение до последних пре делов. Ни китайцы, ни японцы этого назначения никогда не при знают, и все шишки будут валиться на головы несчастных русских. Гайда неистовствует, очевидно, понимая, что чехи нужны до зарезу Омскому Правительству, и последнее готово всё претерпеть, чтобы с ними не ссориться. Плохо было без приятелей, а с ними, кажется, ещё хуже...
28 сентября. Гайда не унимается и издал приказ о назначении Кадлеца Главноначальствующим над всем русским Дальним Вое током; надвигается какое-то чешское пленение; осмелевшие австрийские дезертиры и наши бывшие пленные почуяли свою силу и садятся на наши шеи самым бесцеремонным образом, при пол ном молчании и бездействии союзников...»
Рассказывает Будберг и о том, как Гайда, «всюду ищущий популярности», приказал прицепить к своему поезду два вагона специально для местной молодёжи, едущей поступать в Томский университет, - а в результате вагоны на три четверти оказались заполнены спекулянтами... Подобные сплетни будут потом преследовать Гайду на протяжении всего его пребывания в Сибири. Скажем прямо: первое выступление Гайды в качестве политического деятеля завершилось полным фиаско.
Но здесь же, во Владивостоке, Гайда впервые встретился с адмиралом Колчаком, только что вернувшимся из Японии и ищущим возможности принести пользу Родине. Гайда и Колчак тогда лишь обменялись мыслями о желательности для скорейшей победы над большевизмом сосредоточить всю полноту власти в одних руках - то есть о необходимости военной диктатуры. В этом отношении оба они мыслили совершенно одинаково, и для Гайды эта встреча имела огромные последствия.
6 октября генерал Гайда прибыл в Екатеринбург. Вот каким увидел его в эти дни современник: «Очень молодое длинное лицо, похожее на маску, почти бесцветные глаза с твёрдым выражением крупной, хищной воли и две глубоких упрямых складки по сторонам большого рта. Форма русского генерала, только без погон, снятых в угоду чешским политиканам. Голос его тихий, размеренный, почти нежный, но с упрямыми нотками и с лёгким акцентом; короткие отрывистые фразы с неправильными русскими оборотами». Чрезвычайно точное описание, добавить можно разве что высокий рост и очень крупный нос. По этим характерным чертам его можно сразу узнать на фотографиях, на одной из которых он действительно одет в русскую генеральскую шинель с широкими красными отворотами и чешским нарукавным знаком.
12 октября 1918 года Гайда вступил в командование Екатеринбургской группой войск. Эта группа называлась ранее Северо-Уральским фронтом, и ею руководил произведённый в генералы Войцеховский, который теперь был направлен спасать ситуацию на Самарское направление. Противостоявшая советская 3-я армия М. М. Лашевича уже несколько оправилась от недавних поражений под Екатеринбургом и всё время порывалась перейти в наступление, что вылилось в ряд встречных боев, носивших весьма ожесточённый характер.
В состав Екатеринбургской группы входили как чешские, так и русские части. Последние образовались прямо на фронте, в ходе боев, из местных добровольческих и повстанческих отрядов, они были пока малочисленны и не слишком хорошо вооружены, но отличались твёрдым духом и прекрасными боевыми качествами. Этого уже нельзя было сказать о чехах: все их столь прославленные ранее полки к октябрю явно упали духом (как тогда говорили - «потеряли сердце»). Ведь против них были уже не прежние разнузданные красногвардейские отряды - Троцкий вводил в Красной Армии дисциплину, не останавливаясь перед самыми жестокими мерами. Время лёгких побед кончилось, теперь за любой успех приходилось платить, порой значительную цену. Чехи были к этому не готовы. К тому же, пока они двигались во Владивосток, они знали, что пробивают себе дорогу домой; теперь же они, выполнив свою задачу, мечтали о заслуженном отдыхе - а их вдруг поворачивают обратно на Урал! Сказались и поражения на Волге, где 8 октября была оставлена Самара. В результате по всем частям «Чехокорпуса» слышалось одно и то же требование - скорейшего отвода в тыл.
Что же касается самого Гайды, то он, в отличие от своих соотечественников, был настроен на решительную и непримиримую борьбу с красными до конца. Дело было не только в том, что, овеянный громкой славой «Освободителя Сибири», генерал рвался подтвердить свою репутацию новыми победами. Гайда вообще всё больше ощущал свою общность с Россией, верил, что ему суждено будет сыграть важнейшую роль в её освобождении от красного ига. Его амбиции в этом смысле были очень велики, ему явно была уже слишком тесна роль одного из чешских генералов, он всё более мыслил и действовал как русский Белый военачальник.
Поэтому неудивительно, что значительную роль довелось сыграть Гайде в заговоре, 18 ноября 1918 года приведшем к Верховной власти адмирала Колчака. В начале ноября к Гайде в Екатеринбург из Омска приехал Генерального Штаба полковник Д. А. Лебедев и в откровенной беседе задал вопрос, как отнёсся бы тот к установлению единоличной твёрдой власти. При этом в качестве возможных кандидатов были названы фамилии генералов Болдырева, Иванова-Ринова, Дутова, Дитерихса, а также Атамана Семёнова и адмирала Колчака. По словам Гайды, он сразу назвал фамилию Колчака как наиболее приемлемого из всех. Одновременно он изложил своё политическое кредо, что «только диктатура может спасти страну, но диктатура временная, пока неприятель не будет окончательно разбит». Диктатор же должен быть человеком популярным, широких, достаточно либеральных взглядов, чтобы он мог сплотить вокруг себя нацию и железной рукой проводить среднюю, демократическую линию, не давая перевеса реставраторским кругам. Именно эти идеи и были выдвинуты затем во время переворота 18 ноября. Генерал Гайда, наверное, в мечтах представлял на посту верховного диктатора и спасителя России именно себя, но был достаточно здравомыслящим человеком, чтобы понимать - его кандидатура не пройдёт; в Колчаке же он видел своего единомышленника и надеялся на самое плодотворное сотрудничество с ним.
Через несколько дней в штаб Гайды с инспекционной поездкой прибыл и сам Колчак, тогда военный министр Всероссийского Правительства. По словам Гайды, они проговорили тогда целую ночь, и Гайда убеждал его принять пост Верховного Правителя, в случае, если тот ему будет предложен. Похоже, именно этот разговор окончательно убедил Колчака принять предлагаемую ему власть как свой великий Крест, как предназначение его жизни.
Со своей стороны Гайда заявил, что он не будет принимать непосредственного участия в перевороте, а впоследствии в воспоминаниях так излагал свою тогдашнюю позицию: «Я чехословацкий генерал, - сказал я. - И потому я не имею права вмешиваться во внутренние дела страны, но что касается подчинённых мне русских войск, то обещаю вам, что вся моя армия останется нейтральной... Я в её пределах не допущу вести агитацию ни за диктатуру, ни против. Моя поддержка будет заключаться в том, что я не буду препятствовать офицерам и солдатам признать вас диктатором...»
Именно такая позиция доброжелательного нейтралитета на фронте была необходима для свершения переворота. В этом отношении обещание Гайды стоило очень дорого, и Колчак, придя к власти, сполна расплатился за это.
Дело в том, что положение самого Гайды в этот момент было весьма шатким. Его наступательный агрессивный настрой шёл совершенно вразрез с тенденциями командного и рядового состава чешского корпуса. В это же время политическое руководство из Отделения ЧСНС в России вновь прибирало к рукам власть в корпусе, активно используя распространявшиеся среди легионеров упадочнические настроения. И мятежный Гайда в этом отношении был для политиков из «Отбочки», как кость в горле.
Особенно же активизировались все интриги в конце ноября, когда пришли известия о том, что мировая война закончилась и Чехословакия получила долгожданную независимость. В Сибирь прибыл военный министр новой Чехо-Словацкой Республики генерал М. Штефанек. 5 декабря он приехал в Челябинск, и среди многих организационных вопросов, немедленно вставших перед министром, был и вопрос о Гайде. Стало ясно, что конфликт зашёл уже слишком далеко и места для Гайды среди командования корпуса больше нет. И Штефанек, под давлением политического руководства корпуса, решил убрать Гайду из Сибири, предложив ему «почётную командировку» в Париж, - а это Гайду совершенно не устраивало.