Kraj je omenjen že leta 1016 kot Traskendorf , ko je rimski cesar Henrik II. podaril grofu Viljemu Breže-Selškemu naselje Kozje s 30 kraljevskimi kmetijami, leta 1130 pa je Trachendorf kot dediščine Heme Breže-Selške že v posesti krške škofije. Leta 1197 nastopi prvi kozjanski vitez Oton – Otto de Trachenberch v spremstvu krškega škofa Ekharda.
Preden si podrobneje ogledamo zgodovino gradu je prav, da se seznanimo z legendo, kako je kraj sploh dobil ime, saj je očitno, da gre za domačo žival kozo. Legenda izhaja iz davnih časov, ko je na skalnem Brediču nad dolino Bistrega grabna stal grad s hudobnimi gospodarji. Še hujši od njih pa je bil zmaj, ki je bival v globoki jami v Bister grabnu. Enkrat letno se je prikazal iz brloga in ljudje so mu morali žrtvovati najlepšo mladenko. Z leti so ljudje ugotovili, da zmaj slabo vidi in so mu namesto mladenk dajali že kar starke, potem pa že kar kakšno žival, a zmaj ni zaznal razlike. Sklenili so, da se ga bodo rešili za vedno. Ubili so staro kozo, jo odrli in njen meh napolnili z živim apnom. Zmaj jo je, nič hudega sluteč, pohrustal, potem pa ga je močno zažejalo. Ko se je napil vode iz Bister grabna, ga je zapeklo v drobovju. Zamahnil je z mogočnim repom in za večno izginil v breznu. Tla so se zatresla in grad se je znašel v ruševinah.
Tako pravi legenda, res pa je, da je leta 1511 močan potres porušil kar nekaj gradov na sedanjem prostoru Slovenije. Samo od sebe se pojavlja vprašanje, zakaj v občinskem grbu ni potemtakem koze, saj v njem namesto nje samozavestno nastopa zmaj. A je treba takoj reči, da ne gre za tistega hudobnega zmaja iz Bister grabna, temveč za povsem druge vzroke, ki temeljijo na tradicij, da so številne plemiške družine imele v svojih grbih zmaje kot simbol moči in oblasti. Na Brediču je res bil grad kozjanskih vitezov, o čemer priča tudi bakrorezna podoba iz Vischerjeve Topographie Ducatus Styriae iz leta 1681 na kateri je grad, na Brediču in naselje Kozje s cerkvijo.
Grad Kozje sodi med najstarejše gradove na slovenskem Štajerskem.