Fudbal se u Sarajevu organizovano igrao i godinama ranije, još od samog početka XX vijeka. Sarajevski studenti i đaci su iz raznih krajeva Evrope prenosili popularnost ove zarazne igre. Ubrzo su u gradu krenuli s radom i prvi klubovi. Iako je vrlo brzo rasformiran, ostalo je zabilježeno da je prvi klub u gradu bio Osman. Nakon njega, osnovani su drugi klubovi i neki od njih su do početka dvadesetih godina već izgradili određenu reputaciju, i to ne samo u gradu, već i u širim okvirima. No većina postojećih klubova su u manjoj ili većoj mjeri bili povezivani sa nacionalnim strukturama. Tako su dva vodeća kluba u gradu – SAŠK i Slavija, nezvanično bili klubovi hrvatske i srpske zajednice u Sarajevu. Pored njih, postojali su još Đerzelez i Barkohba, nezvanični klubovi bošnjačke i jevrejske zajednice.

Nasuprot njima, postojao je Hajduk, klub koji se generalno vezao za radničku klasu grada Sarajeva i nije imao podršku bogatijih slojeva unutar nacionalnih struktura. Ipak, sam Hajduk je bio nedovoljan da aktivno uključi sve veći broj zaljubljenika u krpenu loptu pa su sarajevski momci počeli sa organizovanjem drugih timova na neformalnoj osnovi, igrajući prijateljske utakmice. Iz današnje perspektive, ti susreti bi se mogli nazvati utakmicama „raja protiv raje“ na velikom terenu. Jedna takva grupa momaka je, međutim, odlučila otići korak dalje. Mladi radnici željezničke radionice u Sarajevu, kao i sinovi nekih radnika su u jesen 1920. godine odlučili osnovati pravi klub i dogovorili su se oko osnovnih zadataka. S obzirom na to da je dolazila zima, a finansije predstavljale dodatni problem, realizacija ideje je na kraju prolongirana za proljeće. Jedno je bilo sigurno. Njihovi životi su na ovaj ili onaj način bili usko povezani sa željeznicom i izbor imena kluba se nametnuo sam po sebi.

Kao da se već tada moglo naslutiti da će klub u nastajanju pratiti brojne prepreke. Proljeće 1921. godine je konačno stiglo, mladi željeznički radnici su uspjeli kupiti loptu, ali su naišli na problem igrališta. Postojeća igrališta su pripadala drugim klubovima i za njihovo korištenje su naplaćivali naknadu koju mladi momci nisu mogli plaćati. Na kraju su odlučili koristiti vojno vježbalište na Čengić Vili, popularni Egzercir. Prostor je prilagođen potrebama fudbalske igre i prve neformalne aktivnosti su počele. Ubrzo su dogovorene i prve nezvanične utakmice sa drugim sličnim klubovima, ali za veliki iskorak, igranje sa najboljim sarajevskim klubovima, bila je neophodna registracija u Savezu.

U julu 1921. godine je podnesena molba za prijem kluba u Sarajevski podsavez. Mladi i poletni entuzijasti su bez problema ispunili uobičajene administrativne zahtjeve. Nažalost, činilo se da su neki nastajanje novog radničkog kluba vidjeli kao prijetnju pa su naglo uvedeni dodatni uslovi. Uprkos tome, želja je bila dovoljno jaka i 30. jula je nagrađena saopštenjem u kojem je pisalo: „Željeznički športski klub Sarajevo može se primiti za člana Podsaveza tek nakon odigravanja dvije utakmice“. Prema tome, ostalo je još samo da se odigraju dvije utakmice kako bi se dokazalo da je novi klub u stanju bez incidenata organizovati ovakve događaje.

Prva od dvije uslovne utakmice je odigrana na Skenderiji 11. septembra protiv Sarajevskog ŠK. Naši momci se nisu najbolje snašli s malo iskusnijim protivnikom pa je upisan poraz rezultatom 5:1. Drugu utakmicu smo odigrali šest dana kasnije protiv SAŠK-a, tada najjačeg bh. kluba. Odigrana je na stadionu SAŠK-a u Kovačićima. Inače, za ove prilike su u Zagrebu kupljene bijele majice, a na istima se izvezao točak lokomotive sa željezničkim krilima, što je bio i prvi grb na dresu Željezničara. Tim je nastupio u sastavu: Stefan Cicvol, Milan Tomić, Vilim Novak, Rudolf Kefer, Milovan Adamović, Stjepan Katalinić, Ludvig Leple, Dragutin Siber, Dimitrije Dimitrijević, Ivan Krajnc i Franjo Cvelfer. U drugom dijelu su nastupili još Ivan Dunkl i Milutin Egić. Poraz od 1:5 je bio realan odraz snaga između dva još uvijek neravnopravna rivala. No rezultat nije ni bio u prvom planu. Akteri vjerovatno nisu mogli ni pretpostaviti kakvu priču su tog dana pokrenuli. Na taj način je ispunjen i posljednji uslov za punopravno članstvo u Savezu. U ponedjeljak, 19. septembra 1921. godine, Savez je prihvatio novi klub u svoje okrilje i uvrstio ga u takmičarski kalendar Drugog razreda za sezonu 1921/1922.

Od tada, lokomotiva nezaustavljivo ide već deset decenija.