O začiatkoch hradu chýbajú presnejšie správy. Pravdepodobne vznikol v polovici 13. storočia po tatárskom vpáde. Údajne ho v roku 1247 vystaval Lorand z rodu Ratholdovcov. V roku 1280 bolo kamenecké panstvo majetkom Mateja a Ratolda Ratotovcov, ktorí ho v roku 1288 vymenili za majetky Bokšovcov. Výmenu schválil kráľ a synovi komesa Šimona Bokšu potvrdil dedičné vlastníctvo.
Kamenecké panstvo sa stalo vlastníctvom rýchlo sa rozrastajúceho rodu Bokšovcov a tak majetok bolo treba deliť. V roku 1323 pripadol Kamenec Šóšovcom a Zerhadeľovcom. Vtedy sa prvý krát spomína aj hrad Kamenec. Nasledujúce dve storočia viedli tieto dve rodiny o kamenské panstvo boj. To sa samozrejme zanechalo stopy aj na hrade. Roku 1438 sa o ňom píše ako o kamennom hrade s vežou, ktorý treba opraviť.
V roku 1439 zomiera kráľ Albrecht Habsburský a v krajine na dve desaťročia nastáva bezvládie. Zo sťažnosti Šóšovcov v roku 1446 sa dozvedáme, že situáciu zneužil Ján Zerhadeľ a neoprávnene si prisvojil kamenecké panstvo. V tomto roku uhorské stavy zvolili Jána Huňadyho za miestodržiteľa kráľovstva, čím vypukol ostrý boj s Jiskrovým vojskom. Kamenec sa dostáva po smrti Jána Zerhdeľa do správy jeho manželky, avšak Ján Huňady ho v roku 1450 vracia do vlastníctva Juraja a Mikuláša Šósovcov. Onedlho (1451) dobývajú hrad Jiskroví vojaci. V roku 1453 je Jiskra zbavený svojich funkcií, jeho vojsko na Kamenci ostáva a pridáva sa k bratríkom. Osem rokov po obsadení hradu je Kamenec oslobodený kráľovským vojskom Mateja Korvína a vrátený pôvodným majiteľom.
Začiatkom 16. storočia, po smrti kráľa Ľudovíta II. Jagelonského, nastalo obdobie vlády dvoch panovníkov - Jána Zápoľského a Ferdinanda I. Habsburského. V roku 1556 obsadil Kamenec Zápoľského stúpenec František Német, avšak o dva roky ho dobyl späť Ferdinandov generál Imrich Telekeši. Po týchto búrlivých časoch prešiel hrad stavebnými upravami a dostáva svoju konečnú podobu. Na severe bola postavená delová bašta a na opačnej strane pri veži spomínanej v roku 1438 štvorposchodová bašta - dodnes sú zachované pozostatky.
Zo začiatku sa protihabsburský odboj Kamenca priamo nedotýkal, až prezradené Vešeléniho sprisahanie, ktorého sa zúčastnil aj Juraj Šóš. Śóšovci prišli o hrad a v roku 1672 cisárske vojsko obsadilo Kamenec a o rok neskôr ho na výstrahu zničilo. Odvtedy ho nikto neobnovil. Roku 1690 hrad aj s majetkom vrátili s povolením cisára vdove po Jurajovi Šóšovi. V 19. storočí si zemepanská rodina dala pod ruinami hradu vystavať klasicistický kaštieľ.