Piłkarska drużyna STMZ została założona w Kijowie w 1919 roku i reprezentowała Koleje Państwowe (STMZ - to skrót od Towarzystwa Sportowego Kolei Moskwa-Kijów-Woroneż). Chociaż już w 1918 roku zespół związany z koleją o nazwie Sportowe Koło Kolonii Kolejowej (ukr. «Спортивний гурток залізничної колонії» Київ, ros. «Спортивный кружок железнодорожной колонии» Киев) występował w mistrzostwach Kijowskiej Ligi Piłki Nożnej. Na początku istnienia klub nazywał się MKW kolej (Moskiewsko-Kijowsko-Woroneska kolej), SK kolejarzy, Kolejarski SK. Dopiero w 1924 otrzymał nazwę Żełdor (nazwa Żełdor to skrót od Żeleznyje Dorogi, czyli koleje), z którą występował ponad 10 lat. W 1930 roku kiedy zorganizowano Mistrzostwa Kijowa wśród zespołów produkcyjnych, które grali w 9 podgrupach, a potem systemem olimpijskim w meczach finałowych walczyli o tytuł mistrza miasta, klub reprezentował KREZ (Kijowski Zakład Naprawy Wagonów Elektrycznych (ukr. Київський електровагоноремонтний завод). W 1936 zespół zmienił nazwę na Łokomotyw lub z ros.