Die älteste Anlage wurde sicher zur Zeit der Rodung in der ersten Hälfte des 13. Jahrhunderts von den Stadeckern erbaut. Burg und Herrschaft waren spätestens seit 1284 Lehen vom Erzbischof von Salzburg. Der Grund dafür ist nicht ganz klar. Vielleicht hängt er mit dem von 1245 bis 1339 dauernden Streit zwischen den Bischöfen von Seckau und Salzburg und dem Landesfürsten um die zwei Burgen und das Landgericht Waxenegg zusammen, in den zeitweise auch die Stadecker verwickelt waren. 1279 leisteten sie nämlich auf das Landgericht Verzicht und versprachen dem Bischof von Seckau, dessen Besitz "auf der Widem circa Vreunntsperch" zu verteidigen. Diese Gegend Wieden nahmen sie aber in der Folge zu Lehen. Möglicherweise hielten sie es hinsichtlich der Burg gegenüber dem Erzbischof ähnlich.
Von 1329 bis 1434 hatten auch die aus Oberösterreichkommenden Losensteiner nach einer Heirat Besitzanteile an Frondsberg. Diese wurden aber zurückgelöst. Weder die Stadecker noch die Montforter wohnten selbst in Frondsberg, sondern bestellten ritterliche Mannen als Verwalter.
Wer das Grazer Landhaus von Domenico dell'Allio kennt, dem fallen sofort die gleichartigen Säulenarkaden und die gekuppelten Rundbogenfenster auf. Die Inneneinrichtung, die allerdings 1945 sehr gelitten hat, stammt zumeist aus dem 18. Jahrhundert. Der Rittersaal in der Südwestecke enthält eine prächtige Kassettendecke, Gobelins mit Jagdszenen und einen großen Kachelofen mit Delfter Kacheln.
Die Besitzer wechselten häufig: 1615/22 die Pranckh, 1634 Johann Heinrich Flach von Schwarzenberg, 1642 Georg Adl von Adlstein, schließlich 1651 Blasius Lechner, der Verwalter von Frondsberg war und sich bei Pöllau als Sitz einer neuen kleinen Herrschaft das Schloss Lehenshofen erbaute. Beide Herrschaften waren seither vereinigt.
1650 erhoben die Herbersteiner Anspruch auf die Lehenshoheit über Frondsberg, wahrscheinlich wegen einer Famlienheirat mit eim Sarl um 1500, konnten sich aber nicht durchsetzen. Weitere Besitzer waren die Crollolanza, Schick und Saffran. 1823 erwarben schließlich die Reichsfreiherren Gudenus, die um Thannhausen herum mehr als ein halbes Dutzend ehemals selbständiger Herrschaften aufkauften, auch Frondsberg. Sie sind bis heute auf dem Besitz.
1787 wurde als Sohn des damaligen Verwalters auf Frondsberg Karl Schmutz geboren, der 1822/23 ein vierbändiges historisch-topografisches Lexikon der Steiermark herausgab, das für viele historische Fragen auch heute noch als erste Information gut zu gebrauchen ist.