Посчитав, что отечественные специалисты не в состоянии поднять «Динамо», руководители клуба решили поискать тренера за рубежом. Выбор пал на чеха Ярослава Гжебика. По словам генерального директора ФК «Динамо» Юрия Заварзина, новый тренер уверял, что тех игроков, которых он привезет из Чехии, ему хватит для успешной игры на протяжении всего сезона 2004 года. Но по ходу выяснилось, что иноземец часто говорил одно, думал другое, осуществить же пытался третье. Едва познакомившись с командой, Гжебик заявил, что намерен сделать ставку на футболистов-россиян.
Вскоре сообщил, что в команде должны быть футболисты-лидеры. В этой роли, как он говорил, видел двоих — подписавшего в феврале с «Динамо» контракт опытнейшего Андрея Канчепьс-киса и Мартина Гашека (14 матчей за сборную Чехии). В действительности же Гжебик, спровоцировав конфликт с Канчельскисом, постарался при первой возможности от него избавиться, ибо собирался отдать правую бровку своему соотечественнику Влче-ку. Игравший в то время на месте опорного хава Александр Точипин (позиция Гашека) был вскоре отправлен в дубль. Купленный же в ЮАР левый полузащитник Шеппард, способный «перекрыть кислород» еще одному протеже Гжебика — Збончаку, в чемпионате почти не участвовал. Чешский тренер явно лоббировал интересы земляков, не особенно заботясь о том, чтобы в состав проходили действительно лучшие. Однако игравший «пешком», да еще в малом диапазоне ветеран Гашек лидером стать не смог. Остальные чешские легионеры попросту оказались футболистами невысокого класса. С таким же успехом динамовские селекционеры могли набрать игроков в клубах российского первого дивизиона. Стартовали динамовцы в чемпионате неплохо, но вскоре начались неудачи. С каждым туром москвичи все больше теряли уверенность в себе и все ниже сползали в таблице. Так продолжалось семь месяцев, пока Гжебик руководил командой. Смена главного тренера желаемого эффекта не дала. Виктор Бонда-ренко тоже не смог отвести «Динамо» от зоны вылета. Перспектива потерять место в Премьер-лиге на тот момент была у москвичей как никогда высокой. Имея сложнейший финиш, руководство клуба доверило команду пребывавшему не удел Олегу Роман-цеву. Тот с задачей справился. В упорнейшем матче с ЦСКА, от которого зависело все, динамовцы сумели отвоевать столь необходимое им очко, попутно лишив армейцев чемпионского «золота». Межсезонье принесло, казалось, радостную весть: контрольный пакет акций ФК «Динамо» выкупил известный предприниматель Алексей Федо-рычев, состояние которого западные СМИ оценивали в 800 миллионов долларов. Теперь-то уж проблем с деньгами не будет! Федорычев позиционировал себя как давнего поклонника «Динамо», решившего в трудную для клуба годину подставить динамовцам свое плечо.
Он действительно начал с большим размахом. В первенстве динамовцы стартовали с целым отрядом новых легионеров. Из португальских клубов приехали защитники Рибейру и Фре-шо, полузащитники Дании и Лорейру, известный форвард Дерлей и (на вырост) молодой Сисеру. На специально организованной в мае 2005 года пресс-конференции в Тирасполе Федорычев объявил, что он уже вложил в развитие динамовской инфраструктуры 60 млн долларов, и это не предел. Так и оказалось — в период дозаявок в «Динамо» пришли игроки сборной Португалии Манише и Коштинья, чемпион Европы в составе сборной Греции Сей-таридис, вратарь Нуну, нигерийские защитники Овие и Энакархире, игрок сборной России Денис Колодин (из «Крыльев Советов»). По именам «Динамо» нисколько не уступало главным претендентам на чемпионское «золото» — ЦСКА, «Спартаку» и «Локомотиву». Но команды, к сожалению, не получилось. Уже в первом туре динамовцы потерпели разгромное поражение от «Зенита» (1:4). Объединенный общей целью коллектив никак не складывался — португальцы подчеркнуто держались особняком. После одной из тренировок, рассказывали, завязалась массовая драка между легионерами и футболистами-россиянами.
Вскоре подал в отставку Романцев. Ему на смену из Бразилии выписали мало известного в Европе Иво Вортманна. Ходили слухи, что в скором времени «Динамо» должен принять сам Луис Фе-лиле Сколари, а Вортманн появился лишь затем, чтобы подготовить для маститого соотечественника почву. «Временный поверенный» изменить ситуацию в лучшую сторону не смог и после трех поражений на финише отбыл восвояси. На ничего не значащий для «Динамо» матч в Самаре команду вывел уже Андрей Кобелев. Сезон-2006 динамовцы начали под руководством Юрия Семина. Но и тут плодотворного сотрудничества не получилось. Несмотря на то что в межсезонье команду пополнили известные игроки — вратарь Сергей Овчинников, полузащитники Игорь Семшов и Дмит- Молодое будущее Динамо» — братья Комоировы рий Хохлов, динамовцы по итогам чемпионата оказались на рекордно низком в своей российской истории 14-м месте в итоговой таблице. Большую часть сезона футболисты не видели ни зарплаты, ни премиальных. Как выяснилось, истинной цепью прихода в «Динамо» Федорычева было не радение о благе клуба, а совсем другие интересы. Ходили слухи, что миллионер в действительности лелеял надежду на получение права коммерческого использования территории Петровского парка. Когда же где-то с кем-то не удалось договориться, Федоры-чев молниеносно откланялся, прекратив финансирование клуба. В последних турах командой руководил Андрей Кобелев.