Il club fu fondato il 4 luglio 1926. In origine era denominato Radnički sportski klub Borac, traducibile in Club sportivo operaio Borac, con Borac che significa "lottatore", denominazione derivante dai legami tra il club e i movimenti operai locali nella prima metà del XX secolo. Il club fu fondato da un gruppo di amatori del calcio tra cui lo scrittore, attivista ed eroe nazionale della JugoslaviaVeselin Masleša, Rudolf "Rudi" Hiter, Savo Novaković, Nikola Pucar, Brane Pucar, Mustafa Softić, Nikola Kuković, Žarko Vranješević, Mile Stefanović e Brane Stefanović tra gli altri. Furono loro a finanziare il club nella convinzione che in questo modo avrebbero contribuito a promuovere le lotte dei movimenti operai allora in corso. Il nome "Borac" fu dato da Masleša che avrebbe detto: "Se stiamo lottando per i diritti degli operai, perché non dare al club il nome Borac?".[1][2]
Il primo presidente del club fu Rudolf Hiter, mentre Savo Novaković fu nominato vicepresidente. Con la crescita dell'interesse per il calcio in città, Banja Luka ottenne il diritto di organizzare la propria sottolega alla quale afferivano i club dell'intera regione Krajina, e fu edificato un nuovo stadio, più capiente e moderno. L'inaugurazione ebbe luogo il 5 settembre 1937, nel luogo dove sorge l'odierno Stadio municipale di Banja Luka.
Il primo successo del club fu conseguito nel 1928, anno in cui il RSK Borac vinse un torneo disputato an Sarajevo. Prima della seconda guerra mondiale, la squadra principale a Banja Luka era il ŠK Krajišnik, che tuttavia venne sciolto dopo il 1945. Nel dopoguerra il Borac prese il posto del Krajišnik come la principale squadra cittadina. Il Borac disputò delle partite di qualificazione per l'accesso alla Prva savezna liga (il massimo campionato jugoslavo): sconfiggendo il Sloboda Novi Grad per 14–3 (punteggio aggregato), il FK Kozara di Banja Luka per 8–4 (aggregato) e Borac Kozarska Dubica per 7–0 (aggregato) divenne il campione del distretto di Banja Luka. Nel 1945, il RSK Borac cambiò denominazione in FK Borac Banja Luka e militò per un biennio nella lega repubblicana bosniaca, prima di conquistare la promozione nella 2. Savezna liga nel 1948.
Venne promosso, anche se immediatamente retrocesso, per la prima volta nel massimo campionato jugoslavo nella stagione 1961-1962. Ritornato nella massima serie nella
stagione 1970-1971, vi rimase per dieci anni, con una parentesi tra il 1974 e il 1975, in seconda serie. Nel 1974 il Borac raggiunse la finale della Coppa di Jugoslavia, dove fu sconfitta dall'Hajduk Spalato a Belgrado. Tale piazzamento, in virtù della qualificazione dell'Hajduk in Coppa dei Campioni, valse la qualificazione alla Coppa delle Coppe 1975-1976. In tale competizione il Borac superò agevolmente il primo turno imponendosi col punteggio aggregato di 14-1 (9-0 a Banja Luka e 5-1 in Lussemburgo) sui lussemburghesi dell'US Rumelange. La vittoria per 9-0 nella partita di andata a Banja Luka costituisce tuttora un record nelle competizioni europee.[3] Al secondo turno il Borac fu sorteggiato contro il R.S.C. Anderlecht, dalla quale fu eliminata con un complessivo 3-1 (l'Anderlecht vinse poi la competizione). Il Borac Banja Luka fu la sola squadra che riuscì a battere la squadra campione del R.S.C Anderlecht in una partita di quell'edizione di Coppa delle Coppe (vittoria interna per 1–0).
Ritornato in auge alla fine degli anni 1980, il club riuscì a vincere la Coppa di Jugoslavia 1988, e a raggiungere il quarto posto assoluto nel campionato 1990-1991. In totale, il Borac disputò 487 partite nel massimo campionato jugoslavo.[4]
A livello europeo fece propria la Coppa Mitropa del 1992, ultima edizione della competizione.
Nel 2024 la squadra bosniaca esordisce per la prima volta nella sua storia nella Conference League; riuscendo nella sua prima gara ufficiale a pareggiare 1-1 contro la squadra greca del Panathinaikos.