На его фоне развернулся конфликт между Гайдой и начальником Штаба Верховного Главнокомандующего генералом Лебедевым. 26 мая Гайда направил в Омск ультиматум с требованием снять Лебедева, обвиняя того в глупых и вредных распоряжениях, мешающих управлять войсками. Требование это было справедливо по существу: действительно, Лебедев, вследствие своего малого опыта, нередко через голову Гайды отдавал приказы его подчинённым, что только мешало делу. Но заявление было сделано Гайдой в самой недопустимой форме, на грани открытого бунта. В ночь на 30 мая вразумлять Гайду отправился сам адмирал Колчак.
Прибыв в Пермь, адмирал вызвал к себе Гайду и твёрдо объявил ему, что отрешает его от командования Армией за неповиновение приказам. Гайда не ожидал такого поворота, он побледнел и, заметно волнуясь, начал горячо оправдываться, заявляя, в частности, что если его убрать, то вся Армия немедленно побежит. Колчак был непреклонен. Гайде пришлось идти на попятную, он дал слово, что выполнит любой приказ. В свою очередь Колчак склонился к компромиссу: для рассмотрения дела была назначена специальная комиссия под председательством генерала М. К. Дитерихса; на время следствия генерал Лебедев был отстранён от исполнения должности. 4 июня Колчак вместе с Гайдой вернулся в Омск.
Инцидент с Гайдой натолкнул Колчака на мысль о необходимости назначения командующего фронтом, который объединил бы действия всех армий, имея всю полноту власти и полноту ответственности. 11 июня он даже попробовал подчинить Гайде Западную Армию в оперативном отношении, но Гайда, желая «подтянуть» своих новых подчинённых, отдал приказ, в котором пригрозил дисциплинарными взысканиями в случае грабежей и рукоприкладства, чем грубо оскорбил офицеров. Это вызвало всеобщее возмущение, и приказ о подчинении Западной Армии Гайде был отменен.
Теперь оскорбился уже Гайда. К сожалению, он, закусив удила, ударился в политику и представил Колчаку меморандум, озаглавленный «Резюме о военном наступлении». Меморандум этот на самом деле был написан начальником информационного отделения Сибирской Армии штабс-капитаном Калашниковым, эсером, впоследствии поднявшим в декабре 1919 года мятеж в Иркутске. Меморандум требовал как можно скорее собрать Сибирский парламент; объявить о немедленной национализации земли и передаче её крестьянам; призвать на военную службу всю интеллигенцию, отменив существующие для них льготы, а для всех, не состоящих в рядах армии, ввести рабочую повинность и взимать с них особый налог на военные нужды. Были и чисто военные требования - ввести должность командующего фронтом, строго расследовать причины неудач и наказать виновных, а также увеличить жалованье военнослужащим и пенсии их семьям.
Как видим, большинство требований были вполне разумными, но эсеры, как водится, настаивали на немедленном проведении их в жизнь, не учитывая всех сложностей, могущих возникнуть при исполнении требований, иные из которых носили откровенно популистский характер. И вот рупором этих политических кругов теперь оказался генерал Гайда, что не могло не возмутить Колчака.
Решительное объяснение между ними произошло 19 июня 1919 года, во время очередного приезда генерала в Омск. По словам Гайды, он не в силах был терпеть далее такое отношение к себе и сам подал прошение об отставке, а Колчак долго не хотел её принимать, но это маловероятно. Известно, что в результате Колчак дал Гайде годичный отпуск с правом отъезда за границу, чтобы, как он выразился, Гайда мог там «вылечиться от эсеровщины».
20 июня адмирал подчинил Сибирскую и Западную Армии генералу М. К. Дитерихсу. Некоторое время Гайда ещё руководил войсками, но 7 июля Колчак вместе с Дитерихсом прибыли в Екатеринбург с тем, чтобы Гайда сдал командование. Тогда же состоялся и последний разговор Гайды с адмиралом Колчаком. Сам Гайда описывал его потом так: