Istorijat ovog sela počećemo sa legendom o njegovom nastanku:

Neki srpski župan imao je tri kćeri: Kosu, Petru i Soku. Kosa za sebe sagradi grad Kostajnik kod Krupnja, Petra - Petrc ispod Rožnja, a Soka - Soko grad.
 

I danas postoje ostaci starog grada-tvrđave.Tvrđava se pominje u istorijskim spisima iz 1445.godine.
 

O nastanku imena sela postoji više predanja:
 

Po prvom predanju,selo je dobilo ime po stablima Kestena,kojih ima jako puno u ovom selu.
 

Po drugom,nekada davno na brdo iznad sela ,doselio se neki Kosta. Po njemu nasta naziv Kostajnički vis, a samo selo dobi ime Kostajnik.
 

Po trećem predanju Kostajnik dobi ime po nekadašnjem zamku koji se i sam zvao Kostajnik.

 

Tragovi ljudi u ovoj regiji postoje počev od neolita, preko bronzanog, gvozdenog i antičkog doba do srednjeg veka. Na njenom tlu živeli su i smenjivali su se počev od primitivnih ljudi mlađeg kamenog doba, stari Iliri, Kelti, Rimljani, Vizantijci do Slovena, koji su nastanili Rađevinu u VI i VII veku.

 

Početkom XVIII veka u Kostajnik su se doselili: Pivljani, Hercegovci i Birčani. Poreklo familija po prezimenima možete pogledati ovde.