Stari grad Celje so postavili Vovbržani v drugi polovici 12. ali v začetku 13. stoletja. Po izumrtju rodbine, je grad prevzela Žovneška gospoda, ki se je po letu 1341 preimenovala v znamenite Celjske grofe. Ti so mesto Celje in Štajersko dodobra zaznamovali. Grad so začeli spreminjati v bolj udoben stanovanjski prostor, postavili pa so tudi štirinadstropen stolp, ki so ga kasneje poimenovali Friderikov stolp.
Friderik je bil sin mogočnega Hermana, ki se je proti očetovi volji poročil z lepo Veroniko Deseniško. Herman je Veroniko izgnal na grad Ojstrica pri Vranskem, kjer je končala nasilne smrti. Friderika pa je zaprl v stolp, od tu tudi ime stolpa. Ljubezensko zgodbo med Veroniko in Friderikom je opisal tudi Oton Župančič v tragediji Veronika Deseniška.
Po zatonu Celjskih grofov je tudi grad začel propadati. Dele gradu so uporabili za gradnjo dvorca v mestu, nekaj časa pa so ga uporabljali za kamnolom. Ko so leta 1882. ustanovili Muzejsko društvo v Celju, so se tudi za grad začeli boljši časi. Vse do današnjih dni grad počasi obnavljajo.
Danes na gradu prirejajo različne programe, ki so povezani z Celjskimi grofi. Program postanite vitez celjski, kjer se lahko srečamo s Hermanom II ali pa z njeno visokostjo Barbaro Celjsko in poskusimo različne srednjeveške dobrote.