Nazwa miejscowości Prnjavor ma greckie źródło i pochodzi od słowa Pronija, które w bizantyjskim systemie prawno-administracyjnym odnosiło się do dóbr świeckich i kościelnych. Prnjavor był prawdopodobnie własnością (proniją) jednego z pobliskich klasztorów prawosławnych. Wskazywałby na to fakt, że w pobliżu Prnjavoru znajdują się klasztory prawosławne – Stuplje, Liplje, Donji Detlak, Osovica.
Obszar gminy Prnjavor był zamieszkany w czasach prehistorycznych, o czym świadczą znaleziska archeologiczne w kilku miejscach. Najważniejsze ślady prehistorycznej cywilizacji znaleziono na wzgórzu Luščić niedaleko od Banji Kulaši, gdzie znajdowały się pozostałości osad z epoki paleolitu i jedno z najważniejszych miejsc z okresu starszej epoki kamiennej w północnej Bośni, podczas gdy we wsiach Popovici i Štrpci znaleziono artefakty wskazujące na obecność współczesnego człowieka tj. Homo sapiens. Poza okresem prehistorycznym na obszarze gminy Prnjavor znajdują się również wykopaliska archeologiczne, których znaleziska datowane są na okres panowania rzymskiego oraz na okres średniowiecza.
Uważa się, że Prnjavor został założony w XVI w., chociaż pierwsza wzmianka o osadzie Prnjavor pochodzi z końca XVII w. I e na obszarze pomiędzy Vrbasem i Ukriną znajdują się między innymi jeszcze dwie osady: Prnjavor (Bernjavor) i Lišnja (Lessina), małe ośrodki handlowe liczące około 80 domów. Nazwa Prnjavor znajduje się również w dokumencie z 1725 r., a bardziej szczegółowy opis można znaleźć w dokumencie z 1780 r. W XIX w. Wzmianki o Prnjavorze w tekstach pisanych są znacznie częstsze.
Szczególny rozwój miejscowości nastąpił w drugiej połowie XIX w., dzięki rozwojowi handlu i osiedlaniem się tu rodzin zajmujących się właśnie handlem. Dzięki temu powiązały one Prnjavor z innymi społecznościami w Bośni i Hercegowinie, a i poza nią. W swojej działalności szczególnie wyróżniły się rodziny: Trifković, Stanković, Marković, Jovanović, Ostojić, Bajić i inne. Również intensywny rozwój gospodarczy Prnjavor przeżywa pod koniec XIX w., kiedy na te tereny zgodnie z polityką Monarchii Austro-Węgierskiej dotarła duża liczba członków różnych narodowości: włoskiej, ukraińskiej, czeskiej, słowackiej, niemieckiej, węgierskiej, żydowskiej, romskiej i innych. Spis ludności przeprowadzony pod koniec XIX w. I na początku XX w. Potwierdził obecność 19 różnych narodów na tym obszarze i z tego okresu pochodzi nazwa, która określa Prnjavor “Małą Europą” i pozostaje aktualna do dzisiaj. W tym okresie Prnjavor zaczął się prężniej rozwijać w sensie urbanistycznym oraz architektoniczno-budowlanym. Poza obiektami sakralnymi skromnego wyglądu, które już wcześniej istniały w Prnjavorze, budowane są nowe oraz powstają ważne obiekty, które przyczynią się do rozwoju samego miasta. Szczególnie ważny okres rozwoju przypada na lata 1896-1904, kiedy w mieście wybudowano budynek, który miał służyć administracji monarchii Austro-Węgierskiej, szpital, hotel Popović, rozbudowano ulice i place, zasadzono drzewa itp.
W Prnjavorze w 1842 r. Otwarto serbską szkołę wyznaniową, a od roku szkolnego 1886/87 zaczęła działać szkoła państwowa. Po zakończeniu I wojny światowej i utworzeniu Królestwa Serbów, Chorwatów i Słoweńców została tylko jedna państwowa szkoła.
W I wojnie światowej Prnjavor został wyzwolony w dzień świętego Archanioła, 21 listopada 1918 r., kiedy do miasta wkroczyły wojska serbskie pod dowództwem porucznika Ratko Blagoticia. Po zakończeniu I wojny światowej Prnjavor wchodzi w skład Królestwa Serbów, Chorwatów i Słoweńców, a później po reorganizacji terytorialnej z 1929 r. Staje się częścią Vrbaskiej Banowiny i Królestwa Jugosławii. Okres ten charakteryzuje się intensywnym rozwojem gospodarczym i urbanistycznym, a Prnjavor po reformie rolnej staje się powiatem oraz centrum administracyjnym, kulturalnym i edukacyjnym.
W okresie II wojny światowej Prnjavor został wyzwolony 10 czerwca 1943 r. w czasie akcji kozarskiej brygady i oddziału prnjavorskiego.
Po II wojnie światowej, a dokładnie w 1951 r. na terytorium Socjalistycznej Republiki Bośni i Hercegowiny, która była częścią Socjalistycznej Federatywnej Republiki Jugosławii, na obszarze podobnym do dzisiejszego została utworzona gmina Prnjavor, a samo miasto otrzymało funkcję miejskiego centrum administracyjnego. W ciągu ostatnich sześćdziesięciu lat znacząco rozwinęły się tu możliwości gospodarcze oraz infrastruktura, a ośrodek miejski przyjął charakter funkcjonalnego współczesnego miasta, które oddziałuje na okoliczne miejscowości.
