Herenk vjerojatno pripada plemićima srednjovjekovne Slavonije s obzirom na to da je povezan s hercezima i banovima Slavonije te zagrebačkim županima. Herenk je imao tri sina, Marina, Ivana i Petra te Petrov sin i nasljednik Dionizije počinje se u plemićkom pridjevku koristiti imenom Kostajnice, a prvi put je to zabilježeno 1312. godine. Dionizija nasljeđuje sin Petar nakon čije smrti u ime malodobnog Nikole, posjedom upravlja drugi brat Petar (Peto). Nikola Kostajnički posjed preuzima krajem stoljeća. Pretpostavlja se da je za vrijeme njegova života utvrđen kaštel u glavnom sjedištu Kostajnici na unskom otoku. Nepostojanjem nasljednika posjed odlazi u ruke knezova Lipovačkih i susedgradskog gospodara Ladislava Tota. Putem kćeri Ivana Mušina i žene Ladislava Tota, Jelene koja se udaje za Martina Frankopana, Kostajnica 1437. kao i Lipovac, Jasterbarsko i Komogovina postaju posjedi Frankopana. Od vremena Martina Frankopana Kostajnica se spominje kao castrum za razliku od prijašnjeg naziva kaštela (castellum). U tom razdoblju vjerojatno dolazi do pregradnji koje su vjerojatno motivirali nadolazeći sukobi s Osmanlijama. Kostajnica je u posjedu Frankopana do 1471. kada je za 4000 florena ustupljena Ivanu Benvenjudu, a on ju 1494. prodaje Ladislavu Egervarskom. U međuvremenu Kostajnica je u posjedu vranskog priorata. Godine 1528. Kostajnicom upravljaju Zrinski do 1541. kada postaju njezini vlasnici sve do pada pod osmansku vlast. Kostajnica je  bila najvažnija obrambena utvrda u srednjem toku Une, a Zrinski su ju nazivali „glavom i vratima cijele Hrvatske“ zbog čega su ju čuvali više od ijedne utvrde i za obranu trošili najviše novca što su im omogućavali rudnici srebra u Gvozdanskom sve do njihovog zatvaranja kad se Kostajnica s drugim utvrdama prepušta kraljevskoj obrani. Nakon prijetnji 1537. i 1538. kada će pasti Dubica i molbi Nikole Zrinskog da se pomogne utvrdi, čini se da 1552. Kostajnica biva prepuštena krajiškoj vojsci jer se u njoj prema Lenkovićevom izvještaju nalazi njemačka posada od 38 njemačkih pješaka s njemačkim zapovjednikom. U ljeto 1556. Kostajnicu brani posada s više od 60 (63) vojnika kada je grad pod opsadom Malkoč-bega. Obranom je zapovijedao Pankracije Lusthaller, a zanimljivo je da je utvrda predana 16. srpnja, samo dan nakon početka opsade za što se krivilo Lusthallera kako ju je prodao za 2000 dukata čime je pala najbolje utvrđena i branjena utvrda na Uni. Uskoro je zauzet i zapaljen Novi te su tako u jednom mahu pale dvije najvažnije unske utvrde iako postoji i teorija kako je posada Novog nakon vijesti o predaji Kostajnice zapalila tvrđavu i povukla se prema Gvozdanskom. Postoji i priča kako je vojskovođa i zapovjednik Gvozdanskog Toma Lukšić pohvatao kapitulante iz Kostajnice i kaznio ih nabijanjem na kolac te raščetvorio zapovjednika. Novi i Kostajnica postat će utvrde iz kojih će osmanska vojska sljedećih pola stoljeća polaziti na pohode preko Banovine do Pokuplja pa gotovo do Zagreba. Osmanlije su Kostajnicu nadograđivali i održavali u periodu od 1556. do 1688., a zbog brojnosti su na unskom otoku i na drugoj obali gradili vojno selo, palanku. Obnovili su i život u naselju ispod brda Djed, no zbog nemogućnosti da se ovlada prostorom Banovine Kostajnica je preživljavala kao granična utvrda i nesigurno naselje. Krajem 16. stoljeća, pokušalo se vratiti Kostajnicu nekoliko puta od čega je najbolji pokušaj bio 1596. kada su ju napali hrvatski i krajiški vojnici pod vodstvom varaždinskog generala Sigismunda Herbersteina zauzevši naselje na lijevoj obali, prešavši Unu i okruživši utvrdu, ali bez dovoljno snage da konačno zauzmu utvrdu. Utvrdu su pokušali vratiti Zrinski tijekom 17. stoljeća, prvo ban Juraj 1624., a zatim i ban Nikola 1651. što ipak nije polučilo značajnijeg uspjeha. Kostajnica je oslobođena za vrijeme rata 1683.-1699. kada je ban Nikola Erdody 1687. krenuo prema Kostajnici, ali bez dovoljno vojne sile. Sljedeće godine s banskom vojskom stiže i vojska Ludovika Badenskog koji donosi 15 topova većeg i manjeg kalibra te za samo tri dana uspješno zauzimaju kostajnički Stari grad te 1688. godine. Ovo je pokrenulo lančanu reakciju kojom su ubrzo oslobođeni Dubica i Jasenovac. Nakon oslobođenja, ubrzo je došlo do nove borbe, ovaj put političke, za Kostajnicu i područje između Une, Save i Kupe, protiv presezanja njemačkih staleža i centralističke vlasti. Odmah po oslobođenju u Kostajnici se gradi velika barokna u zemljana utvrda na Djedu, no slabljenjem značaja Kostajnice radovi su generalno na ovom području bili u sve većoj stagnaciji. Razvitkom trgovine s Bosnom, prioritet su dobile druge zgrade potrebne za zaštitu trgovine ili od epidemija. S vremenom je Kostajnica postala gradić te prometno, gospodarsko i trgovačko središte regije. Ukidanjem Vojne krajine 1871. Stari grad postupno gubi vojno-stratešku moć i uskoro biva napušten.

Nad mjestom na uzvisini Djed, početkom 18. stoljeća je tlocrtno stajala kvadratna utvrda s čardakom u središtu. Uskoro je započela i gradnja bastionske utvrde kojom je kvadrat trebao dobiti šiljate izduljene bastione na uglovima te raveline prema I i Z. Prikaz stanja iz cca 1713. bilježi planiranu utvrdu i dijelove koji su već tada postojali, SZ bastion te dio kurtina prema I i J. Ono što je tada i možda nakon toga sagrađeno registrirano je na Weissovu crtežu iz 1729. Do promjene dolazi 1735. kada pod vodstvom graditelja F. du Portal de Monteaua započinje gradnja nove utvrde. Njezina je koncepcija bitno drugačija, no može se pretpostaviti kako su dotad podignuti dijelovi mogli donekle biti integrirani u novu gradnju. Tlocrt iz 1736. pokazuje da je bio predviđen izduljen oblik s polubastionima na uglovima te trokutnim istacima na čelnim stranicama. Oko bedema imao je biti jarak te skriveni put i glasija. Stanje 1750. sadržano je u jednom ne posve jasnom prikazu, vidljiva su dva dijela utvrde, sjeveni i juzni, prikazana različito i razdvojena bedemima. Očigledno je u to doba bio dovršen južni zid, a sjeverni je bio planiran ili se na njemu tek radilo. Utvrda nije bila izvedena posve prema Du Portalovu projektu, o čemu nam svjedoče današnji ostaci i prikazani druge polovice 18. stoljeća, poput tlocrta utvrde koji potječe iz okvirno 1773. Nije naime bio načinjen SI polubastion pa je nastao deformiran, asimetrični oblik kojim je utvrda smanjena. Već krajem stoljeća je zapuštena vjerojatno i napuštena te postupno propada. Do danas su sačuvani razmjerno znatni ostaci utvrde na brdu Djed. Tok bedema i šančeva ocrtava tlocrtni oblik nekadašnje utvrde. U njezinu prostoru uređeno je izletište s parkom.

Stari grad je relativno velika peterokutna utvrda koja se oblikom približava trokutu. Visoke kamene zidine okružuju prostor dimenzija 58,5×49 metara. Na najjužnijoj točki koja je okrenuta desnoj obali i gdje se spajaju JZ i JI zid, nalazi se okrugli kameni bastion. Pokraj bastiona u istočnom se bedemu nalazi ulaz u grad. Na zapadnom se uglu uzdiže peterokutna kula, a na mjestu loma sjevernog bedema, koji danas zbog nanosa samo dijelom prat korito rijeke Une, uzdize se najstarija i najmarkantnija te po sačuvanim detaljima i najznačajnija četverokutna kula. Različitost triju kula upućuje na slojevitost i različita vremena izgradnje kao i na brojne nadogradnje i preinake te rušenja nastala ratom ili vremenom. Utvrda je već dugo u vlasništvu općine koja je 1907. sanira najugroženije dijelove, posebno srušenih bedema uz rijeku.. Gjuro Szabo posjećuje utvrdu 1916. te preporučuje radove koji će se vršiti 1930-ih, ali će njih poništiti šteta prouzrokovana u Drugom svjetskom ratu. Nakon rata utvrda je bila puna smeća, u bastionu su se pekli janjci za obližnju gostionicu. Stari grad upisan je u registar spomenika kulture 1957., izvršene su neke sanacije, a lokalni nogometni klub u četverokutnoj kuli smješta svoje prostorije, a izviđački odred u peterokutnoj. Radovi na Starom gradu vršili su se 1973.-1990., a izbijanjem rata u rušenjem mosta na Uni, Stari grad ostao je van državnih granica Hrvatske na neko vrijeme. Istraživanja provedena do 1990. utvrdila su 6 razvojnih faza grada, a njegova četvrta po redu smatra se najvrjednijom te se zbog toga smatralo kako se u obnovi ona treba istaknuti.