Šoštanj castle (german Schönstein - beautiful stone) was probably built in the second half of the 12^th century which can be presumed from the architectural characteristics of the ruins (the tower) above the town. In the document of which origins date between 1993 and 1220 brothers Eberhard and Herman from Šoštanj (de Schonenst(ein)) are mentioned. We meet the same liegemen of Šentpavel in Šoštanj in 1236 as witnesses of archbishop of Salzburg, like many times before. As early as 1201 and then in the next decades Eberhardus et Hermannus de Sonensteine are mentioned as liegemen and witnesses of Ekbert, bishop of Bamberk. Because of the family ties between lords of Drava and lords of Šoštanj, when lords of Drava are free of Spanheim connections in the second half of the 12^th century, Šoštanj estate becomes allodium (Kos, Vitez in grad). When knights of Šoštanj died out in 1268 (by T.Ravnikar's opinion from around 1286 on) the estate was passed over to counts of Heunburg. In 133 the knight (probably castellan) is mentioned named Pfafflina. He is mentioned once more the same year and again in 1318 (purch Schonstain), which represents the first explicit mentioning of the castle. The same year the emperor granted the to Herman of Heunburg the right to sell the castle to Dietrik Wolfsauer, bishop of Lavant, but counts of Heunburg probably soon bought it back. In 1322 when Herman of Heunburg died fortification was inherited by Friderik freiherr of Žovnek, son of Katarina, née countess of Heunburg, and pawned the fort on December 29^th 1330 to lords Wlasee but only for a short period. The castle was then the property of Counts of Celje until 1456, when their family died out.
As a manager for lords of Celje in 1436 Jošt Vaist is mentioned and soon after, maybe in 1439 lords of Celje demolished the castle themselves (Counts of Celje chronicles) so the Habsburgs wouldn't take posession of it. Nevertheless castellans of Šoštanj were witnessed later as in the year 1448 Anthony Grimschitzer (from Grimšice near Bled?) and 1456 Andrej Trebniški who was defending the castle before the emperor but soon made truce with him and kept the castle in pawn. In 1459 it was bought by Krištof Narringer for 400 pounds. It is more probable that the castle was demolished by Turks in 1473. In any case in 1503 it is mentioned as an ancient fort.

An opinion exists, which states that in some historical sources (including the first mentioning) Schönstein does not represent Šoštanj castle but some other castle in Lungau in Carinthia or Stria of somewhere in Lavant (Kos).