Piłkę nożną w Prijedorze zaczęło grać na początku XX wieku, dokładnie pod koniec I wojny światowej i wyzwoleniu spod panowania Austro-Węgier. Pierwszy klub piłkarski w Prijedorze powstał w 1919 roku i nazywał się Prijedorski Fudbalski Klub Slavija.
23 maja 1928 roku w miejscowości górniczej Ljubija, w pobliżu Prijedor, został założony FK Rudar Ljubija, którego członkami byli głównie górnicy oraz mieszkańcy Ljubiji i okolic. Pierwszy oficjalny mecz Rudar Ljubija rozegrał z Hajdukiem Prijedor i wygrał 2-1. Na początku istnienia klub nie brał udziału w oficjalnych zawodach Królestwa Jugosławii. Podczas II wojny światowej, klub zawiesił działalność.
Prawdziwy wzrost klubowej piłki nożnej w Prijedorze rozpoczął się po zakończeniu II wojny światowej. W Prijedorze powstało wiele klubów: Grmeč , Željezničar, Žitopromet, Jedinstvo, Mladost. Pierwszy oficjalny mecz Rudar rozegrał w 1947 z Podgrmeč Sanski Most. W następnym roku zbudowano stadion w Ljubiji. Tego samego roku Rudar debiutował w Pucharze marszałka Tito. W 1952 roku przyszedł pierwszy poważny sukces górników - 2.miejsce w lidze obwodowej i w barażach o awans do Ligi Republikańskiej Jugosławii (trzeci stopień) był lepszym od swego rywala Borac Banja Luka.
W 1954 roku w Prijedorze założono FK Celuloza, a w 1958 roku FK Mladost i FK Celuloza połączyły się w FK Radnički. W 1965 roku FK Željezničar połączył się z FK Radnički w OFK Prijedor. W kolejnych dziesięcioleciach OFK Prijedor i FC Rudar Ljubija współpracowali między sobą.
Od 1962 roku Rudar Ljubija występował w międzystrefowej lidze. W 1967 klub zdobył historyczny awans do grupy zachodniej II ligi jugosłowiańskiej. W tym samym roku, Rudar Ljubija przeniósł się na nowy stadion w Prijedorze i zmienił nazwę na FK Rudar Ljubija-Prijedor. W 1970 roku górnicy dotarli do 1/16 finału Pucharu marszałka Tito. W sezonie 1970/71 klub walczył w kwalifikacjach do pierwszej ligi jugosłowiańskiej z FK Proleter Zrenjanin, ale przegrał rywalizację (0:5, 1:0). W następnym sezonie ponownie zakwalifikował się do barażów do I ligi, ale ponownie przegrał tym razem z FK Spartak Subotica (2:2 na wyjeździe, 1:3 u siebie). W 1973 klub spadł do III ligi. W 1976 powrócił do II ligi, ale w 1979 ponownie spadł do III ligi. W 1981 klub okazał się w lidze regionalnej (IV poziom), dopiero po dwóch sezonach powrócił do III ligi. W 1985 z triumfem powrócił do drugiej ligi. Niestety, po sezonie 1987/88 nastąpiła reforma systemu lig, dlatego Rudar okazał się w nowo powstałej między-republikańskiej lidze (III stopień). Zaledwie po roku, w 1989 wrócił do drugiej ligi W rozgrywkach o Puchar marszałka Tito dotarł do półfinału, gdzie w rywalizacji z Velež Mostar przegrał dopiero w serii rzutów karnych 3:5 (0:1 w Mostarze, 1:0 w Prijedorze).
Kiedy w 1992 roku wybuchła wojna w Jugosławii klub przestał działać. Po zakończeniu wojny w 1995 roku powstał nowy FK Rudar-Prijedor, w skład którego weszły byłe piłkarze Rudaru Ljubija i OFK Prijedor. W 1995 przegrał w finale Pucharu Republiki Serbskiej z FK Borac Banja Luka (2:2, 2:3). Od 1995 roku występował sezonów w pierwszej lidze serbskiej. W 2001 spadł do 2 drugiej ligi serbskiej. W 2002 system lig w Bośni i Hercegowinie został reformowany i pierwsza liga serbska okazała się na II poziomie. Po dwóch sezonach nieobecności powrócił do pierwszej ligi serbskiej. W 2005 do klubu przyłączył się miejscowy rywal OFK Prijedor. W sezonie 2008/09 zajął 1. miejsce w pierwszej lidze serbskiej i awansował do Premijer ligi.
