The club was founded in 1954, as the railway club, therefore it was sometimes called ŽFK Lokomotiva. In the past they played their matches on the home ground of FK Rabotnički, and so often youth players from Rabotnički came to the club for development. Many decades later it moved to the current stadium location in Skopje settlement Karpoš. To the older generation it was known as Komunalec, because on that field played FK Komunalec, and also the club FK Vanila, but now neither team exists anymore. Lokomotiva for the first time in its history during the 2007/08 season, played in the Macedonian Second League.