Klub je osnovan 1925. godine. U Jugoslaviji takmičio se Drugoj saveznoj ligi. Iako je najčešće bio u vrhu nikad nije uspio da je osvoji. Svoj najveći uspjeh FK Leotar je postigao u sezoni 2002/03 kada je osvojio prvo mjesto u Premijer ligi Bosne i Hercegovine i plasirao se u kvalifikacije za Ligu šampiona.
Leotar svoje utakmice igra na stadionu Police koji je kompletno obnovljen 2003. godine prije utakmice u kvalifikacijama za Ligu šampiona. Kapacitet stadiona je 4.500 sjedećih mjesta. Stadion je takođe obnovljen i pred novi nastup fudbalera Leotara u Premijer ligi BiH 2021. godine, postavljene su komplet nove stolice, urađena atletska staza, semafor, unutrašnjost svlačionica, proširene pres lože, asfaltiran i zatvoren južni dio stadiona, a u planu je renoviranje terena i postavljanje reflektora.[1]
