Jedan od rijetkih sarajevskih klubova prije Prvog svjetskog rata koji nije nosio nacionalni predznak bio je Radnički sportski klub Hajduk Sarajevo. Klub je nastao kao radničko sportsko društvo sa željom da okuplja i predstavlja sve radnike grada Sarajeva.
Počeci organizovanog fudbala u Sarajevu vezuju se za period kada je ova igra postajala sve popularnija među sarajevskom omladinom. Na sastanku održanom 1913. godine u Hrasnom, na inicijativu Ivana Petrinića, osnovan je RSK Hajduk. Klub je dobio ime po poznatom splitskom Hajduku. Osim Petrinića, osnivačkom sastanku prisustvovali su Ivan Dorfer, Josip Valetić, Milan Egić, Vladislav Benko, Adolf Kete i Stevo Sicvol, radnici zaposleni u tvornicama Butazzoni, Raher i Babić, kao i radnici željezničke radionice te stanovnici Doca i Hrasnog.
Prve klupske dresove nabavio je Ivan Petrinić. Dresovi su bili ljubičaste boje sa žutim okovratnikom i manžetnama. Prvu finansijsku pomoć klub je dobio od Kancira, povjerenika u tvornici Butazzoni, i Mustafe Toromana, radnika željezničke radionice.
Godine 1914. za šest kruna iznajmljeno je zemljište u Hrasnom, na kojem je uređeno prvo igralište kluba. Međutim, zbog nedostatka finansijskih sredstava za redovno plaćanje zakupa, igralište je ubrzo ugašeno.

Tokom Prvog svjetskog rata klub je prestao sa radom. Nakon završetka rata, u oktobru 1918. godine, članovi se ponovo okupljaju i nastavljaju djelovanje u duhu ideja zbog kojih je klub i osnovan. Zajedno sa Slavijom Sarajevo iznajmljuju zemljište na Skenderiji, koje je bilo u vlasništvu Islamske zajednice, te grade novo igralište.
U tom periodu Hajduk ostvaruje svoje prve velike uspjehe. Klub postaje prvak Sarajeva 1920. godine, a titulu osvaja i u prvenstvu 1920/21. godine. Kada je Slavija 1925. godine izgradila vlastiti stadion na Marijin-Dvoru, igralište na Skenderiji ostalo je u potpunom vlasništvu Hajduka.

Posebno značajan događaj za RSK Hajduk desio se 27. i 28. maja 1928. godine, kada su svečano otvorene tribine Radničkog stadiona na Skenderiji. Tim povodom organizovan je veliki turnir radničkih klubova Bosne i Hercegovine. Na turniru su nastupili Hajduk (Sarajevo), Borac (Višegrad), Borac (Banja Luka), Borac (Jajce), Proleter (Teslić), Željezničar (Sarajevo), Borac (Sarajevo), kao i druga ekipa Hajduka. Pobjednik turnira bio je domaći Hajduk. Prilikom otvaranja stadiona iznad njega je podignuta crvena zastava, koju je podigao Radmilo Grđić. Klub je nastupao u crvenim dresovima i bio je član organizacije radničkih sportskih klubova Jugoslavije.

Prva fudbalska utakmica pod reflektorima u Sarajevu odigrana je 1932. godine na stadionu Skenderija. Organizator ovog događaja bio je Hajduk Sarajevo, koji je tom prilikom ugostio ekipu Splita iz Splita.

Najveći uspjeh u Kraljevini Jugoslaviji Hajduk je ostvario u sezoni 1935/36, kada je učestvovao u kvalifikacijama za ulazak u Prvu ligu Jugoslavije. Klub je zauzeo drugo mjesto u kvalifikacionoj grupi u kojoj su nastupali Hajduk Split, Slavija Sarajevo i Osvit Šibenik. Time je izborio plasman u završnicu kvalifikacija za ulazak u Prvu ligu, gdje je poražen od zagrebačkog HAŠK-a.

Godine 1937. Hajduk je obilježio 25 godina postojanja. Tim povodom u listu „Snaga“ objavljena je „Hajdukova spomenica“, svojevrsni historijat kluba. Organizovan je i veliki turnir na stadionu Skenderija na kojem su nastupili Hajduk II, Hrasničar, Sloga, JOŠK, SAŠK, Slavija, Đerzelez, Željezničar, Velež, Visoko, Željezara, reprezentacija Beograda, Radnički iz Kragujevca te domaćin Hajduk Sarajevo. Pobjednik turnira bio je Hajduk Sarajevo.
Posljednji veliki uspjeh prije početka Drugog svjetskog rata klub je ostvario u sezoni 1939/40, kada je postao prvak Sarajevskog nogometnog podsaveza.

Nakon ulaska Jugoslavije u Drugi svjetski rat i uspostavljanja Nezavisne Države Hrvatske na području Bosne i Hercegovine, klub se prijavio za takmičenje u ligi NDH za sarajevsku regiju. U tom periodu klubu je dodat sufiks „H“, što je bila obaveza za sve klubove koji su nastupali u takmičenjima NDH.
Jedan od najvažnijih događaja iz tog perioda desio se 1941. godine, kada su izgorjele tribine stadiona na Skenderiji, zbog čega Hajduk nije mogao igrati na svom stadionu. Godine 1942. klub obilježava 30 godina postojanja velikim turnirom na kojem su nastupili Hajduk (Sarajevo), Bata (Borovo), Radni (Osijek), Zagorac (Zagreb), Zagorac (Varaždin), HAŠK (Zagreb), Đerzelez (Sarajevo), HAŠK (Novo Sarajevo) i SAŠK (Sarajevo). Pobjednik turnira bio je Hajduk Sarajevo. Godine 1944. klub je proglašen HRS-ovim (Hrvatski radnički savez) klubom za Bosnu i Hercegovinu.

Nakon sloma NDH i formiranja nove Jugoslavije, RSK Hajduk Sarajevo prestaje sa radom. Razlozi za gašenje kluba bili su višestruki. Pored činjenice da je nastupao tokom perioda NDH, novo vrijeme donijelo je osnivanje novih sportskih društava i gašenje velikog broja predratnih klubova. Kao jedan od razloga navodi se i podatak iz knjige „Sarajevo u revoluciji“ (tom I), u poglavlju Eriha Koša „Djelatnost KPJ u oblasti kulture“, gdje se ističe da je klub bio pod utjecajem komoraša i policijskih krugova predvođenih braćom Jakšić, koji prije Drugog svjetskog rata nisu dopuštali djelovanje Komunističke partije i njenih članova unutar kluba.

Pored fudbalske sekcije, Hajduk je imao i veoma uspješnu sekciju teške atletike, odnosno hrvanja. Među najistaknutijim članovima bio je Uroš Miletić, višestruki prvak Jugoslavije u hrvanju. Tokom Drugog svjetskog rata proveo je period od 1941. do 1945. godine u koncentracionom logoru Jasenovac, a nalazio se među posljednjim grupama zatočenika koje su premještene prije konačne likvidacije logora. Nakon rata vratio se svom poslu u željezničkoj radionici i više od dvadeset puta bio proglašavan udarnikom rada. Istaknuti hrvači kluba bili su i Gojko i Vlado Uzelac te Svetozar Ćuk.

Među najpoznatijim fudbalerima koji su nastupali za RSK Hajduk bili su Franjo Glaser, jedan od najpoznatijih jugoslavenskih reprezentativaca, Sergej Demić, također reprezentativac Jugoslavije, Alojz Stanarević, Josip Fogl, Ivan Dorfer, Ivan Krajnc, Ivan Vanek, Anton Til, Stjepan Kenig, Musaja Čelebičić, Mijo Lasić, Vilim Kumerle, Karlo Čubelić, Ludvig Kebat i Ljubo Filipović.
Među najistaknutijim članovima uprave kluba bili su Vojo Marković, Mika Knežević, Spaso Janjić, Vladeta Bilbija, Drago Futur, Ivan Šalamunović te Bogdan i Dušan Stanišić.