El club nasqué el 1925. Debutà per primer cop a la Lliga de la República de Srpska la temporada 1995-96.[1] La temporada 2001-02, el Leotar guanyà la darrera lliga de la Republika Srpska abans d'ingressar a la lliga nacional bosniana.[2] En la seva primera temporada a la lliga bosniana la temporada 2002-03 es proclamà campió, impedint al Zeljeznicar el tercer campionat consecutiu.[3] Com a conseqüència, la temporada següent disputà la Lliga de Campions de la UEFA, en la qual derrotà el Grevenmacher de Luxemburg i fou vençut pel club txec Slavia Praga.
