Jméno   mĕsta Prnjavor  je  řeckého původu a pochází ze slova Pronia, který v byzantském administrativním a správním systému znamenal sekulární a církevní majetek. Prnjavor je pravděpodobně byl pronie  jednoho ze některých nedalekých ortodoxních klášterů. Tohle je podpořeno skutečností, že v bezprostřední blízkosti Prnjavoru jsou kláštery Stuplje, Liplje, Donji Detlak, Osovica.

Oblast obce Prnjavor byla osídlena od pravěku, o čemž svědčí archeologická naleziště na několika místech. Nejvýznamnější stopy prehistorické civilizace byly nalezeny na kopci Luščić v blízkém okolí lázní Kulaši, kde se nacházejí pozůstatky osídlení z doby paleolitu a jedno z nejdůležitějších lokalit z doby starší doby kamenné v severní Bosně, zatímco v vesnicích  Popovići a Štrpci byly nalezeny artefakty naznačující přítomnost moderního člověka, tj. homo sapiens. Kromě prehistorického období má oblast Prnjavoru také lokality, které patří do období římské vlády a období středověku.

Předpokládá se, že Prnjavor vznikl v 16.století, i když první písemná stopa osídlení Prnjavoru pochází z konce 17.století a nachází se v rakouské vojenské zprávĕ neznámého autora z let 1688 až 1699.  Zpráva zaznamenává, že v oblasti mezi dvĕmi řekami Vrbas a Ukrina se mimo jiné nacházejí dvě menší osady: Prnjavor (Bernjavor ) a Lišnja ( Lessnia),   malý trh, každá má 80 domů. Zmínka o Prnjavoru je také nalezena v jednom zápisu z 1725 a podrobnější popis Prnjavoru je z roku 1780.  V 19.století se Prnjavor v písemných pramenech objevuje mnohem častĕji.

Ve druhé polovině devatenáctého století zažíva mĕsto zvláštní pokrok vývojem obchodu a obchodních rodin, které jsou Prnjavor pripojily ve vĕtší míře k ostatním oblastem v Bosně a Hercegovině a take  mimo ni.V tomto smyslu jsou významné rodiny Trifkovič, Stankovič, Markovič, Jovanovič, Ostojič, Bajič a další. Také intenzivnější hospodářský vývoj Prnjavor zažívá koncem XIX. století, kdy se podle politiky vládnoucího Rakousko-Uherska v této oblasti usídlilo velké množství příslušníků různých národů: Italové, Ukrajinci, Češi, Slováci, Němci, Maďari, Židé, Romové a jiné národy. Sčítání lidu provedené koncem 19. a počátku 20. století potvrdilo přítomnost 19 různých národů v této oblasti a od té doby zůstalo jméno „Malá Evropa“, jak  i dnes označují tuto oblast. Tehdy Prnjavor zažívá větší urbanizaci a rozvoj z architektonického a stavebního hlediska. Kromĕ posvátných objektů skromného vzhledu, které existovaly v dřívějších dobách, staví se nové budovy, budují další významné objekty, které přispívají k fyzionomii místa. Obzvlášť důležité období je od roku 1896 do roku 1904, kdy byla v Prnjavoru postavena budova, která bude sloužit jako sídlo okresních důstojníků

jmenovaných rakousko-uherskou vládou, dale nemocnice, hotel „Popović“, ulice jsou rozšířeny a byly postaveny chodníky , zasazena část stromů do alejí a pod.

V Prnjavoru v roce 1842 byla otevřena srbská, konfesionální škola a od školního roku 1886/87 začíná pracovat státní komunální škola, a po skončení první světové války a vytvoření Království Srbů, Chorvatů a Slovinců pracovala v Prnjavore pouze státní škola.

V první světové válce byl Prnjavor osvobozen na den sváteho Archandĕla 21.listopadu 1918, kdy do města vstoupila srbská armáda v čele s poručíkem Ratkem Blagotičem. Po skončení  první světové války se okres Prnjavor stal součástí Království Srbů, Chorvatů a Slovinců nebo později s novou státní teritoriální reorganizací z roku 1929, se stal součástí Vrbaské bánoviny a Království Jugoslávie. Toto období se vyznačuje intenzivním hospodářským a městským rozvojem a Prnjavor se po agrární reformě stal centrem okresu a administrativním, kulturním a vzdělávacím střediskem.

Prnjavor byl osvobozen 10.července 1943, v druhé světové válce,  v akcí Páté kozarské brigády sa Prnjavorským oddílem.

Po druhé světové válce, přesnĕji v roce 1951, jako součást SR Bosny a Hercegoviny a SFRJ,  na ploše přibližnĕ dnešní, vznikla obec Prnjavor a město Prnjavor dostalo funkci městského správního střediska.  Za posledních šedesát let se v této oblasti vyvíjejí významné ekonomické kapacity a infrastruktura a městské centrum přebírá charakteristiku městského osídlení, díky čemuž jedná v sousedních vesnicích ve funkčním smyslu.