2004-2005
Накануне сезона команду покинули четыре волейболиста стартовой шестерки, найти которым адекватную замену не удалось. Это и предопределило результат сезона. В кубке России "Локомотив-Изумруд" впервые в своей истории не смог выйти в "Финал четырех", из Кубка ЕКВ выбыл в 1/8 финала, а в национальном чемпионате финишировал только шестым (худший результат с 1993 года).
2005-2006
Впервые с 1995 года "Локомотив-Изумруд" не играл в еврокубках, поэтому главной целью сезона было возвращение в Европу. Для решения этой задачи в Екатеринбург были приглашены два игрока сборной Кубы - Оделвис Доменико и Генри Белл. К сожалению, они присоединились к команде только в декабре и совсем не в той форме, какую от них ждали. В розыгрыше Кубка России "Локомотив-Изумруд" после годичного перерыва сумел выйти в "Финал четырех", но занял там только третье место. В чемпионате России команда не смогла попасть в пятерку лучших (что гарантировало возвращение на международную арену) и завершила сезон только на седьмом месте.
2006-2007
Начало сезона у екатеринбуржцев не сложилось. В декабре "Локомотив-Изумруд" не смог на своей площадке выиграть полуфинальный раунд Кубка России, а из первых шести матчей чемпионата проиграл четыре. Однако постепенно команда набрала ход и сумела выполнить задачу, поставленную на сезон - занять пятое место и вернуться в еврокубки.
2007-2008
Накануне сезона клуб покинули 4 игрока стартовой шестерки, два из которых играли в команде ключевые роли - это Николай Апаликов и особенно Александр Герасимов. Как следствие сезон получился бочкой дегтя с небольшой ложкой меда.
На внутренней арене "Локо" полностью провалился. В Кубке России он не смог выйти в "Финал четырех", а в чемпионате и вовсе занял 12 (последнее) место. И только на международной арене - в розыгрыше кубка вызова - "Локо" показал достойный себя результат. Уральцы дошли до финала, где уступили прославленной итальянской "Модене".