Prethodnik Slobode je klub osnovan davne 1919. godine pod imenom Gorki koji je zabranjen 1924. godine. Nakon zabrane Gorkog i Hajduka, dvaju radničkih športskih klubova iz Tuzle, tri godine u Tuzli nije bilo takvih društava, a svaki pokušaj obnove nekog takvog društva osujetila je policija. Aktivisti su se uporno zalagalii i uz želju velikog broja radnika 20. studenoga 1927. godine, u Tuzli je osnovano Radničko-kulturno sportsko društvo Sloboda, s četiri sekcije: športskom, tamburaškom, horskom i diletantskom. Članovi nogometne momčadi športske sekcije bili su Karlo Mott, Jozo i Nikola Kemenc, Suljo Nezirović, Alfred Puhta, Safet i Ešo Isabegović, Oto i Ivica Milanović, Josip Leder, Muho Mujezinović, Karlo Švarc, Vlado Mileusnić, Rihard Žlebnik, Mujo Begić, a prvu utakmicu odigrali su sa Solvajem iz Lukavca. Kulturno-prosvjetno društvo i RSK Slobodu vodili su socijaldemokrati od 1927. do 1932. godine , ali u oba društva su unatoč ilegalnih uvjeta za rad, stalni i trajni utjecaj imali komunisti. Početkom 1928. godine športska sekcija se osamostalila i postala samostalni klub pod imenom Radnički sportski klub “Sloboda”. Uspostavom Šestosiječanjske diktature Sloboda je bila na zubu režima koji je po svim radničkim organizacijama nesmiljeno udarao i vršio pritiske kao na protudržavne elemente. Sloboda je zadnju utakmicu uspjela odigrati Sportskim klubom Šumadija 8. svibnja 1932. godine. Vrlo brzo iste godine, na jednom sastanku igrača i UO Kluba socijaldemokrata Jozo Jurić, koji je tad predsjedavao RKPD Sloboda, izjavio je da obustavlja rad Kluba na pola godine, s time da će svakom igraču koji želi dati ispisnicu radi prelaska u drugi klub. U stvari je ovo značilo zabranu rada RSK Sloboda koju je policija sprovela uz znanje i punu potporu socijaldemokrata. Nakon ovog dio igrača napustio je Tuzlu ili prestao igrati.[1] 1939. Sloboda je igrala u sastavu Miralem Mandžić, Zvonko Herljević, Džemal Mandžić, Franjo Manger, Pašaga Vugić, Fikret Ibrišimović, Tonči Pavlić, Džemal Hadžihrustić, Mustafa Salković-Mućak, Boško Popović-Popac, Raif Mujezinović, Nezir Mujezinović, i Alija Mutičević. Predsjednik je bio Mehmedalija Hukić.
