Pred kraj 16. stoljeća, sjeverno od nahije Uskoplje, u nahiji Trijebavi bilo je formirano još jedno novo gradsko naselje. To je kasaba Jenidže Jajce (Novo Jajce), kako je prvobitno nazvan današnji Mrkonjić-Grad. Osnovao ju je Hadži Mustafa-aga, porijeklom iz tog kraja, podigavši na tome mjestu kao svoj vakuf prve kulturnoprosvjetne i druge objekte. Tako o nastanku Varcar-Vakufa, današnjeg Mrkonjić-Grada, piše Adem Handžić u rezultatima svog iscrpnog istraživanja objavljenog pod naslovom O formiranju nekih gradskih naselja u Bosni u XVI stoljeću.
U Handžićevom su radu zapisani svi detalji, kako o mjestu nastanka gradića, tako i o njegovom utemeljitelju. Tako Handžić piše kako je to područje na kojem se danas nalazi Mrkonjić-Grad došlo pod osmansku vlast padom jajačke banovine (1528), da je prvobitno pripadalo nahiji Zmijanju, koja se prostirala sjeverno od današnjeg Mrkonjića, s lijeve strane Vrbasa, a bila je naseljena samo vlasima-stočarima, koji su pripadali carskom hasu. Godine 1540. ili 1542. ta je nahija obuhvatala 21 selo, dvije stare varoši (Greben i Bočac), tri utvrđena grada (Greben, Bočac na Vrbasu i Dubica, danas selo sjeverozapadno od Mrkonjića), jedan naseljen čifluk s ukupno 250 vlaških domaćinstava.
Taj čifluk, naseljen s pet domaćinstava, predstavljao je dijelove graničnih sela prema ključkoj tvrđavi, Donja i Gornja Rakova, drugim imenom Stražilice, a bio je u posjedu dvojice čifluk-sahibija: Hasana, sina Jusufova, mustahfiza u tvrđavi Udlbini, i Ferhada, sina Jusufova iz Uskoplja. Međutim, u nahiji se spominje još jedan čifluk kome su pripadala dva sela: Donje Trijebovo i Srednje Trijebovo, za koja stoji da su pripadala čifluku umrlog Hurem-paše. Selo Trijebovo bilo je važno kao sjedište nahije, ali je interesantno što su u selu Gornjem Trijebovu spomenuti Hadži Mustafa, osnivač kasabe, kao i njegov otac Mehmed-beg.
Za historiju nastanka i prvobitnog razvitka kasabe Novo Jajce postoje, piše Handžić, dva prvorazredna savremena izvora koji jedan drugog dopunjavaju. Jedno je sačuvana zakladna povelja Hadži Mustafa-aginog vakufa, a drugo opširni popis bosanskog sandžaka iz početka XVII stoljeća. Treba spomenuti i živu tradiciju o džamiji i porijeklu njenog osnivača. Tradicija, naime, kaže da je Mustafa-aga sin pravoslavnih roditelja, od porodice Đukanovića iz susjednog sela.
Međutim, o Hadži Mustafa-aginom porijeklu, o njegovoj visokoj dvorskoj službi i o motivima osnivanja vakufa i formiranja time gradskog naselja postoje izričiti podaci u njegovoj vakufnami. Ta vakufnama, napisana na turskom jeziku, ovjerena je pred sudom u Istanbulu između 16. 9. 1594. i 5. 9. 1595. godine, ali je, čini se, džamija bila podignuta nešto ranije, oko 1592. godine.
Tu se kaže da je Mustafa-aga, kizlaraga, sin Mehmed-bega i Aifa-hatun, a Mehmed-beg sin Abdulveduda, rodom iz mjesta Yayce yenicesi (Novo Jajce) u Bosni u Rumeliji. Pored drugih kvaliteta koji su pobrojani, ističe se da je bio vrstan poznavalac arapskog jezika i šerijatskog prava. Tu se navodi kako je Mustafa-aga uvidio da je tom mjestu potrebna džamija, jer je na putu i prometno mjesto, te je odredio da tu podigne džamiju. Istodobno je dao sagraditi mekteb, karavan-saraj, han od 20 soba, 24 dućana i jednu pekarsku furunu. Za funkcioniranje i održavanje tih objekata ostavio je gotov novac. Podizanjem tih objekata, početkom zadnje decenije XVI stoljeća i utvrđivanjem redovnog sedmičnog pazarnog dana, to mjesto steklo je osnovne uvjete da bude proglašeno kasabom.
Položaj kizlarage bila je visoka funkcija na carskom dvoru u Istanbulu. Bilo je to zvanje trećeg age po rangu na dvoru. Ta se funkcija, piše Handžić, u našim izvorima spominje u različitim varijantama, ali uvijek u istom značenju. U vakufnami se precizno navodi kizlaraga, međutim, u navedenom popisu Mustafa-aga označava se samo kao aga u carskom dvoru. U drugom izvoru, popisnom defteru, navedeni su, opet, zemljišni posjedi Mustafa-age i njegova oca Mehmed-bega, što upotpunjuje navode vakufname. Iz tih podataka saznajemo još i to da mu je i otac bio na službi u carskom dvoru.
U selu Trijebovu Mehmed-beg je posjedovao dvije, a sin mu Mustafa-aga jednu baštinu. Zatim je Mehmed-beg imao jedan posjed (zemin) u selu Gornjoj Kloki, koji je zatim, s još tri slična imanja, prešao u posjed njegovog sina Mustafa-age. Tekst o posjedu u Gornjoj Kloki na plastičan način opisuje formiranje današnjeg Mrkonjić-Grada kao gradskog naselja. Riječ je o većem kompletnom posjedu kao i tri druga posjeda koja je on faktički držao i na tom Mustafa-aginu posjedu započela je urbana gradnja gradskog naselja. Tu stoji: Kasaba Gornja Kloka, drugim imenom Novo Jajce. Zemini Mehmeda, sina Nesuhova, i Mehmed-bega i Husejna i Miloša u korištenju Hadži Mustafe, age u carskom dvoru. Spomenuti aga je na tim zeminima dao sagraditi časnu džamiju, karavan-saraj i dućane. Pazarni dan je ustanovio u petak.
Prilikom ponovnog popisa bosanskog vilajeta stigao je carski ferman datiran posljednje dekade mjeseca safera 998. godine između 30. 12. 1589. i 8. 1. 1590. godine, čiji je sadržaj sljedeći: Uvaženi jajački kadija dostavio je u svojoj predstavki da se Gornja Kloka, drugim imenom Novo Jajce, koje pripada jajačkom kadiluku, budući da je granično mjesto, vrlo teško prolazno i opasno, to su granične age, islamski ratnici i narod tog kraja podnijeli molbu da se u tome mjestu podigne časna džamija, karavan-saraj i dućani te da to mjesto postane kasaba, što bi za putnike, trgovce, goste i stanovništvo tog kraja bilo vrlo korisno. Budući da je zamoljena carska zapovijed o tome da se niko ne treba miješati u pitanje onih koji ovamo s porodicama dolaze i nastanjuju se, to je od strane carskog Divana izdata zapovijed da to mjesto postane kasaba...
Handžić se u svom radu detaljnije osvrće i na porijeklo osnivača grada Mustafa-age. Nije tačno, dakle, da je Mustafa-aga direktno sin kršćanskih roditelja, ali je tačno da je rođeni sin s tog područja i kao takav je vjerovatno kršćanskog porijekla. Pitanje je samo ko je od njegovih predaka prešao na islam. Ako znamo da je ova oblast došla definitivno pod tursku vlast padom jajačke banovine (1528), onda je neki predak poslije te godine primio islam. Ako tu činjenicu analiziramo, proizlazilo bi sljedeće: Ako se Mustafa-aga oko 1592. godine isticao u poznavanju šerijatskog prava i arapskog jezika, te dospio do položaja kizlarage, morao je tada imati najmanje 45 godina. Ako dalje uzmemo starosnu razliku između oca i sina od najmanje 20 godina, onda je pad Jajca mogao zateći Mustafina oca kao dijete.
Vrlo je, dakle, vjerovatno da je Mustafin otac, još kao dijete dospio na carski dvor, islamiziran, dobivši ime Mehmed i školovan. Ime Mustafinog djeda Albdulvedud, što znači Božiji rob, očito je eufemističko i krije kršćansko ime. Takva psihologija zapaža se gotovo kod svih tadašnjih konvertita koji su bili na višim položajima te su navodili eufemistička imena roditelja kršćana.
Mehmed je u službi napredovao, dobio titulu bega i na kraju zvanje carski sluga. Nažalost, nedostaju popisi za dug period, od 1574. do 1604. godine, da bismo na osnovu zabilježenih posjeda njegove porodice konkretnije utvrdili njegovo porijeklo.
Od objekata Mustafa-agina vakufa do danas (u trenutku kada je Handžić pisao tekst) očuvana je samo džamija, i to, čini se, uglavnom originalna. Neki zahvati u prošlosti predstavljali su rekonstrukcije koje nisu promijenile originalnu arhitekturu. Podignuta je oko 1592. godine jer su te godine u Istanbulu izrađena dva svijećnjaka od mjedi na kojima je ugraviran tekst u kojem stoji da ih je naručio aga carskog dvora Mustafa-aga i zavještao ih za svoju džamiju u mjestu Jenidže Jajce. Tu je izrađena i kletva za onoga ko ih iz džamije otuđi. Do danas se očuvao samo jedan originalni svijećnjak-šemadan, dok drugi predstavlja kopiju kasnije izrade. Posljednji put obnavljana je pod rukovodstvom tadašnjeg mutevelije tog vakufa Mehmed-efendije Adžemovića.
Kao godine popravki džamije spominju se i 1883, 1899. i 1925. godina. Nakon izgradnje džamije, iz Istanbula je donesen veliki ćilim, težak oko 300 kilograma, kojim je pod džamije bio zastrt i koji su austrougarski vojnici 1878. godine prilikom pljačke rasjekli na četiri dijela, od kojih se jedan dio i danas čuva u Umjetničkom muzeju u Beču.
Vojne i policijske snage RS-a, uz naklonost tadašnjih civilnih vlasti, Kizlaraginu džamiju zapalili su i minirali 1993. godine. Potom je srušena, a materijal je odvezen na deponiju smeća koja se nalazi na lokalitetu Grabež. Generalna direkcija vakufa Republike Turske osigurala je sredstva i džamija je obnovljena.
Kizlaragina džamija u Mrkonjić-Gradu je smještena u centru grada, tik to zgrade Opštine. Komisija za očuvanje nacionalnih spomenika Bosne i Hercegovine u maju 2005. godine donijela je odluku o proglašavanju džamije nacionalnim spomenikom Bosne i Hercegovine.