Hrad dal postaviť pravdepodobne v r. 1253 - 1270 na mieste starého hradiska Ivankov syn Ondrej, účastník bitky pri Slanej. Najstaršie jadro hradu vymedzoval hradobný múr neskororománske opevnenia, ktoré uzatváralo trojuholníkové nádvorie. Na južnej strane, na vyvýšenine bola hranolová veža s obytnou a obrannou funkciou. Koncom 13. storočia pristavali ďalšiu vežu. Medzi veže postavili potom paláce v spoločnom opevnení. V tejto podobe poznal hrad Matúš Čák Trenčiansky a takto stál až do 15. storočia

Pôvodne v polovici 13. storočia nebol postavený hrad Gýmeš v takom rozsahu. Veľký hrad vznikol v neskoršej dobe a to spojením resp. opevnením viacerých menších budov, resp.hradov, ktoré boli postavené v tesnej blízkosti. V období medzi 9. a 13. storočím na mieste zvanom Pustý Gýmeš bolo desať menších osád, z ktorých ostala jedna a to obec Jelenec. Prvá písomná zmienka o obci pochádza z roku 1113, keď obec Gýmeš sa uvádza v súpise majetkov zoborského kláštora benediktínov.