A vár pontos építési ideje egyelőre nem ismert, de annyi magabiztosan kijelenthető: több szakaszban készült, minden évszázad rajta hagyta a keze nyomát. Ami elsőre a szemünk elé tárul a várból, az az Oltalom-bástya, a vár 5 ismert bástyájából az egyik legrégebbi. Ne tévesszen meg a formája: bár a kerekségéből adódóan inkább toronynak lenne illő nevezni, a várháborúkban földdel feltöltve erősítették meg, és így tökéletesen funkcionált bástyaként is, és sokkal jobb állapotban vészelte át az évszázadokat, mint a többi védmű.
Mit tudunk a vár legkorábbi időszakairól? Nagyon keveset… A Gesta Hungarorum szerint a honfoglaló magyar törzsek már szláv telepeseket hódoltattak be Nógrádon. Aztán az ezredforduló környékén I. (Szent) István király a vármegyerendszer megszervezésekor egy vármegye központjává teszi. A történelmi Nógrád vármegyének azonban nem a mértani középpontjában vagy ahhoz közel helyezkedik el a vár, ahogy mai megyének sem: a délnyugati csücskében található. Ne feledjük: István idejében nem Buda volt a központ, hanem Esztergom, és innen kiindulva a vármegye első meghatározó erőssége volt Nógrád. Hasonló logika fedezhető fel az egykor szomszédos Hont és Heves vármegyék esetében is.