Hrad vstúpil do písaných dejín v diele Gesta Hungarorum (Činy Maďarov), dokončenom na začiatku 13. stor. Prameň hovorí o veľkej pevnosti, nazývanej údajne Boršov Zvolen. Založenie hradu spája s legendárnym vojvodom Boršom, čo však z iných zdrojov nemožno potvrdiť. Hrad mohol vzniknúť v 12. storočí súčasne s utvorením územnosprávnej jednotky Zvolenského komitátu. Sídlo vystupuje v ďalších prameňoch pod ustáleným názvom Zvolen, alebo Zvolenský hrad. Po vybudovaní mladšieho Zvolenského zámku začali pramene postupne používať aj názov Starý hrad. Súčasné označenie Pustý hrad nachádzame od záveru 18. storočia.
Nemožno vylúčiť, že počas vpádu do Uhorska v rokoch 1241 – 1242 sa Tatári (Mongoli) dostali až do Zvolena. O osudoch mesta i hradu v tom čase nemáme správy. Vieme však, že v roku 1243 kráľ Belo IV. obnovil Zvolenu výsady, ktoré mesto stratilo počas tatárskeho vpádu. Hrad bol vyhľadávaným miestom pobytov panovníka. Vo Zvolene sa dokonca konala svadba Belovej dcéry Konštancie a haličského kniežaťa Leva.
Rozbroje a feudálna anarchia v poslednej štvrtine 13. stor. neobišli ani Zvolenský hrad. Jeho správcom bol dlhoročný zvolenský župan Demeter. Aktívne sa zúčastnil konfliktov medzi súperiacimi šľachtickými rodmi, avšak s jeho menom spájame aj razbu falošných mincí na Zvolenskom hrade. V dôsledku Demeterovho konania obsadilo hrad kráľovské vojsko, ale ovládal ho i oligarcha Matúš Čák.
Po upokojení pomerov zostal hrad sídlom zvolenského župana. Spravoval ho Demeterov synovec Donč, ktorý sa podieľal na zavádzaní hospodárskych a územných reforiem. Územie podliehajúce hradu sa v 30. rokoch 14. storočia zmenšilo rozčlenením komitátu a utvorením Zvolenskej stolice. Novým sídlom panovníkov pri ich pobytoch vo Zvolene sa stal zámok (gotický kastel) vybudovaný v susedstve mesta. Starý hrad naďalej slúžil úradníkom, vojakom i remeselníkom.
Význam hradu opätovne vzrástol v polovici 15. storočia. Zvolen s priľahlým regiónom vtedy kontroloval český veliteľ Ján Jiskra, zastupujúci v Uhorsku práva ovdovenej kráľovnej Alžbety. Počas bojov medzi znepriatelenými stranami napadol Jiskrov najväčší rival Ján Hunyadi (Huňady) aj Zvolen. Na sídlo Jána Jiskru zaútočil v rokoch 1447 a 1451. Nevieme však, či dobýjal hrad, alebo zámok. Vypálené bolo pritom ľahšie prístupné mesto.
Vojnové udalosti a náročná údržba zrejme prispeli k spustnutiu starého Zvolenského hradu v závere stredoveku. K čiastočnému obnoveniu jednej z funkcií hradu došlo v čase osmanského ohrozenia. Starý hrad slúžil na pozorovanie okolia a vysielanie varovných signálov pred nepriateľskými vojskami. Prítomnosť hliadky na hrade podporila vartovka, novovybudovaná strážna veža. O jej výstavbe sa rozhodlo v roku 1564.
Po ukončení osmanských nájazdov v 17. storočí hrad stratil strategický význam. V spoločenskom vedomí ho nahradili povesti. Najznámejšou je povesť o zakliatom Barátovi. Podľa rozprávania zaznamenaného v 19. storočí údajne strážil poklady na Pustom hrade zakliaty mních s konským kopytom namiesto nohy. Ľuďom, ktorí sa zatúlali na hrad naháňal smrteľný strach. Zjavoval sa im ako pustovník, alebo aj ako zviera.