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 vezivao 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 i ubrzo 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. Naposlijetku 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 im 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. Naročito su „glasni“ bili predstavnici klubova sa nacionalnom pozadinom koji su osjetili da bi klub za sve mogao predstavljati ozbiljnog konkurenta u budućnosti samim tim što će imati širu bazu igrača. 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 17. septembra protiv SAŠK-a, tada najjačeg bh. kluba. Ona i danas ostaje ubilježena kao prva zvanična utakmica našeg kluba, premda klub još uvijek nije bio formalno primljen u Savez. Odigrana je subotnjeg popodneva na stadionu SAŠK-a u Kovačićima, tada perifernom sarajevskom naselju. Za tu priliku 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. Prvi pogodak koji je postigao Dimitrije Dimitrijević i simbolika tog dana su nešto što ostaje za sva vremena. Akteri vjerovatno nisu mogli ni pretpostaviti kakvu priču su tog dana pokrenuli.

Već sutradan, odigrana je i druga uslovna utakmica. Poraz od 2:1 protiv Sarajevskog ŠK je značio da je Željezničar bez problema odigrao i drugu utakmice te tako ispunio 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ć više od devet decenija.