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