During the time of former Yugoslavia, FK Sloboda was active in the Yugoslav First League and the team had much success, despite never winning the title. The best result was achieved in 1977 when FC Sloboda has qualified for the UEFA cup 1977–78. Unfortunately, Las Palmas from Spain was stronger, 5–0 in Spain for Las Palmas and 4–3 for FK Sloboda in Tuzla. This is a club with very rich history in former Yugoslavia giving many stars such as Mesud Nalić, Omer Jusić, Rizah Mešković, Mersed Kovačević, Fuad Mulahasanović, Ismet Hadžić, Dževad Šećerbegović, Mustafa Hukić, Midhat Memišević as well as young players members of U-20 national team such as Isanović, Ćulumarević, Milošević, Hajrulahović, Jogunčić.