[[Grad]] ali [[utrdba]] je bil najbrž zgrajen v drugi polovici [[12. stoletje|12. stoletja]] na fevdni posesti Šentpavelskega samostana, vendar graditelji niso znani. Šoštanjski vitezi so se v virih pojavili med letoma 1189 in 1268. Šentpavelska fevdnika Eberharda in Hermana srečamose sreča v Šoštanju leta 1236 kot priči salzburšega nadškofa. Ta rod Šoštanjskih je posest z gradom alodiral ter potem izumrl sredi [[13. stoletje|13. stoletja]]. Sam grad se v listinah izrecno omenja šele leta 1318 kot purch Schonstain. Grad in gospostvo sta bila tedaj alod Vovbrških, po mnenju Toneta Ravnikarja od približno leta 1286. leta dalje, ko so prevzeli posest, ter gornjegrajsko in krško odvetništvo od Kraigov, prvotnih krških odvetnikov na tem področju. Vovbrški so utrdbo imeli v lasti do leta 1322, saj je po njihovem izumrtju Šoštanj pripadel svobodnim gospodom [[Žovneški gospodje|Žovneškim]], ki so ga leta 1329 zastavili sorodnikom Wallseejevcem. [[Celjski grofje]] so zadržali grad, gospostvo, šoštanjske fevde in trg vse do izumrtja leta 1456. Za Žovneško-[[Celjski grofje|Celjske]] so grad upravljali njihovi kastelani. Leta 1387 je Šoštanj v zameno za [[Grad Krško|Krško]] in [[Grad Vipava|Vipavo]] dobila v preužitek vdova grofa [[Herman I. Celjski|Hermana I.]], [[Katarina Kotromanić|Katarina]]. Kot celjski upravnik gradu se leta 1436 omenja Jošt Vaist, nato trški sodnik Hieronim Voitländer.
V bojih s [[Habsburžani]] so Celjani sami delno porušili Šoštanj. Kasneje se še omenja Šoštanjski gradiščan, ampak le do začetka 16. stoletja, ko nastopije nastopil njegov propad. Leta 1470 cesarje imenujecesar za oskrbnika urada Šoštanj in Kacenštajn imenoval svojega svetnika Andreja von KraigKraiga.
