El FK Sarajevo va ser fundat el 24 d'octubre de 1946 amb la fusió dels clubs Udarnik i Sloboda. El seu primer nom va ser S.D. Torpedo. Jugà el seu primer partit el 3 de novembre i l'any següent canvià el nom a S.D. Metalaca Sarajevo, abans d'adoptar el nom actual el 1949. Ràpidament ascendí a la primera divisió iugoslava on es mantingué de forma estable quasi totes les temporades. L'any 1967 es proclamà campió iugoslau per primer cop, trencant un seguit de triomfs serbis i croats. L'any 1985 repetí campionat, amb jugadors destacats com Safet Sušić.