La squadra è stata fondata nel 1919 come "FK Gorkij"; ciò la rende una delle più antiche società della Bosnia ed Erzegovina. Sloboda, in molte lingue di derivazione slava, significa "libertà". Durante il periodo jugoslavo, la società disputò diverse stagioni di massima serie, non riuscendo comunque mai a conquistare alcun titolo: il miglior risultato è il terzo posto ottenuto nella stagione 1976-1977, alle spalle di Stella Rossa e Dinamo Zagabria, con conseguente qualificazione alla successiva Coppa UEFA. Ai trentaduesimi lo Sloboda affrontò gli spagnoli del Las Palmas, che vinsero facilmente la gara d'andata in territorio spagnolo; 5-0 il risultato finale. Il ritorno in Jugoslavia si concluse con una vittoria per 4-3 dello Sloboda, che non servì a ribaltare il pesante rovescio dell'andata.
Con l'indipendenza della Bosnia ed Erzegovina, la squadra ha partecipato quasi ininterrottamente, pur con alterne fortune, a tutte le edizioni del massimo campionato nazionale. Non ha mai vinto il titolo ed ha come miglior risultato il terzo posto, ottenuto in due occasioni: nel 1995-1996 e nel 2008-2009. Oltre alla coppa UEFA cui partecipò negli anni Settanta, vanta anche due apparizioni nella Coppa Intertoto, nel 2003 e 2004.
Lo Sloboda ha raggiunto 4 finali di Coppa nazionale (1 Coppa di Jugoslavia, 3 Coppe di Bosnia), perdendo in tutte le occasioni: nel 1971 perse contro la Stella Rossa; nel 2000 arrivò seconda in un girone finale alle spalle dello Željezničar; nel 2008 fu sconfitta dallo Zrinjski Mostar e l'anno successivo dallo Slavija.
Lo Sloboda fu la squadra protagonista delle due edizioni della Kup prvoligaša, la Coppa di Lega jugoslava. Vinse nel 1971-72 battendo 1-0 in finale lo Željezničar e fu finalista nel 1972-73 battuto dalla Stella Rossa (0-0 al Tušanj e 0-2 al Marakana).
Wikimedia Commons contiene immagini o altri file su Fudbalski klub Sloboda Tuzla