W rundzie wiosennej sezonu 1994/95 do klubu został zaproszony znany trener Wałerij Wodian, z którym w 1996 klub osiągnął swój pierwszy najwyższy sukces - mistrzostwo Ukrainy.
18 kwietnia 1998 Łokomotyw Odessa "trzasnął drzwiami" w swoim ostatnim oficjalnym meczu w historii pokonując Wuhłyk Makiejewka - 28:4. To zwycięstwo jest nadal największym w historii ukraińskiego futsaluЗубастый дебютант «покусал» львовян… / 3492 дня Одесса не видела большого футзала - www.sport.ua.
Do 1998 grał w najwyższej klasie rozgrywek ukraińskiego futsalu. W związku z sytuacją finansową w kraju Kolej odmówiła sponsorowania Łokomotywa i po "złotym" sezonie 1997/98 klub został rozwiązany. Drużyna rezerw przeniesiona do pierwszej ligi i po sezonie 1998/99 Łokomotyw Odessa przestał istnieć ostatecznie.
Barwy klubowe, strój BłękitnyBiały Zawodnicy klubu zazwyczaj grali swoje mecze domowe w błękitnych koszulkach, białych spodenkach i błękitnych getrach.
Sukcesy Trofea międzynarodowe
Klubowe Mistrzostwa Europy w Futsalu: półfinalista (1x): 1996/97
Trofea krajowe
Pozostałe trofea Międzynarodowy Turniej "Biała Akacja" (w Odessie): 1 miejsce (1x): 1996, 1997 Międzynarodowy Turniej "Kijowska Ruś": 1 miejsce (1x): 1995
Piłkarze i trenerzy klubu Futsaliści