Grad Šoštanj (nem. Schönstein - lepi kamen) je najbrž zrasel v drugi polovici 12. stoletja, kar dopuščajo arhitekturne značilnosti grajskih razvalin (stolpa) nad naseljem. V listini, nastali med letoma 1193 in 1220, se omenjata brata Eberhard in Herman iz Šoštanja (de Schonenst(ein)). Ista šentpavelska fevdnika srečamo v Šoštanju leta 1236, tokrat spet, tako kot že nekajkrat poprej, kot priči salzburškega nadškofa. Že leta 1201 in nato še v naslednjih desetletjih se Eberhardus et Hermannus de Sonensteine omenjata kot fevdnika bamberškega škofa Ekberta in njegovi priči. Zaradi sorodstvene vezi med Dravskimi in Šoštanjskimi, postane ob osvoboditvi Dravskih spanheimskih vezi v drugi polovici 12. stoletja, šoštanjsko posestvo kasneje alod (Kos, Vitez in grad). Z izumrtjem Šoštanjskih vitezov leta 1268 (po mnenju T. Ravnikarja od približno leta 1286 dalje) preide posest v last Vovberških. Leta 1311 se omenja vitez (verjetno gradiščan) v imenu Pfafflina. Omenja se še enkrat istega leta in nato še leta 1318 (purch Schonstain), kar predstavlja prvo izrecno omembo gradu. Istega leta je bila Hermanu Vovberškemu s strani cesarja odobrena prodaja gradu lavantinskemu škofu Dietriku Wolfsauerju, ki pa so ga Vovberžani verjetno že kmalu odkupili nazaj. Leta 1322, ko je Herman Vovberški umrl, je utrdbo podedoval Friderik svobodni Žovneški, sin Katarine, roj. grofice Vovberške in jo nato 29. decembra leta 1330 zastavil gospodom Walseejem, a le za kratek čas. Grad je potlej ostal v posesti Celjskih vse dotlej, dokler njihov rod leta 1456 ni izumrl.
Kot celjski upravnik gradu se leta 1436 omenja Jošt Vaist, že kmalu nato, morda leta 1439, pa naj bi Celjani grad sami razdejali (Kronika celjskih grofov), da bi se ga ne polastili Habsburžani. Kljub temu pa so šoštanjski gradniki izpričani še pozneje, tako leta 1448 Anthony Grimschitzer (iz Grimščic pri Bledu?) in leta 1456 Andrej Trebniški, ki je takrat branil grad pred cesarjem Friderikom, vendar pa se je z njim kmalu pomiril in utrdbo obdržal v zastavi. Leta 1459 jo je odkupil Krištof Narringer za 400 funtov. Verjetnejše je torej sporočilo, da so grad leta 1473 razdejali Turki. Vsekakor se omenja leta 1503 že kot gradišče.

Obstaja mnenje, da v nekaterih zgodovinskih virih (vključno s prvo omembo) Schönstein ne predstavlja ravno obravnavanega šoštanjskega gradu ampak nek grad v Lungau na Koroškem oz. Štajerskem ali nekje v Lavantu (Kos).