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