Lokomotiw, tak jak 12 stycznia 1936 roku zostało utworzone ochotnicze towarzystwo sportowe „Lokomotiw”, które przejęło pracowników transportu kolejowego
Wiosną 1936 debiutował w Grupie W Mistrzostw ZSRR, w której zajął ostatnie 8 miejsce i jesienią 1936 startował w Grupie G.
W 1937 ponownie występował w Grupie W.
Zajął 2 miejsce w Grupie W i po reformie systemu lig ZSRR awansował do Grupy A, jednak nie utrzymał się w niej. Zajął 17 miejsce i spadł do Grupy B. W 1940 występował pod nazwą Łokomotyw Piwdnia lub Lokomotiw Juga.
II wojna światowa przeszkodziła prowadzić rozgrywki w latach 1941-1945.
Po zakończeniu wojny klub w 1946 startował w Trzeciej Grupie, strefie Centralnej jako Łokomotyw.
Później występował tylko w rozgrywkach lokalnych. W 1973 zmienił nazwę na Czerwona Striła, ale po roku wrócił do nazwy Łokomotyw.
W sezonie 2021/22 zespół startował w rozgrywkach Amatorskiej ligi Ukrainy, zajmując 10.miejsce w grupie 1, w następnym sezonie awansował na 5.pozycję w grupie 2.
Latem 2023 roku klub zgłosił się do rozgrywek Drugiej ligi (D3) i otrzymał status profesjonalny.