Die Burg wurde von der Familie Stainer zu Beginn des 13. Jahrhunderts errichtet. Ihre Mitglieder waren Ministeriale der Grafen von Clam-Velburg, besaßen aber Innernstein als freies Eigen. Erster namentlich bekannter Burgherr war Chunradus de Stainer, der um 1209 in einer Urkunde aufscheint.

1292 übergab Herbord von Stein seinen Eigenbesitz an Ulrich von Capellen und nahm ihn umgehend als Lehen wieder zurück. Als die Capeller 1406 ausstarben, ging die Lehenshoheit an die Liechtensteiner über. Diese blieben bis in das 19. Jahrhundert Lehensherren von Innernstein. 1424 verkaufte Jörg von Stein sein Lehen den Brüdern Sigmund und Wolfgang Steinbeck. 1499 gelangte die Burg an Oswald von Schweinbach.

Sein Neffe Ulrich veräußerte sie 1517 an Veit Flußhart. Dessen Nachkommen ließen 1509 die Burg in ein wohnlicheres Renaissanceschloss umbauen. 1611 erlosch auch die Familie Flußhart. Ihr Erbe war Hans Georg von Sebisch. Da er ein Anhänger der Lehren Luthers war, musste er während der Gegenreformation Innernstein an Sigmund von Mühlheim verkaufen. Dieser gab die Herrschaft aber 1633 an Tobias Helfried von Kaiserstein weiter. Sie blieb nun fast hundert Jahre bei dessen Familie, bis sie Ernst von Kaiserstein 1731 an Johann Friedrich von Stiebar verkaufte.

1804 übernahm Johann Freiherr von Rosenberg das Schloss, das aber schon 1819 von Karl Graf Clam-Martinic erworben wurde. 1876 veräußerte Graf Heinrich Jaroslaw Clam-Martinic den Besitz an seinen Schwager, Siegfried Hugo von Salm-Reifferscheidt, von dem er 1897 an die Freiherren von Tinti überging. Sie behielten Innernstein bis 1969. Dann erwarb die Familie Brandner aus Wallsee die teilweise bereits vernachlässigte Anlage und begann sie mit beträchtlichem Aufwand zu restaurieren. Seit 1994 gehört sie der Familie Nossek aus Wien.

Weitere Informationen: Burgen Austria