Der Baubeginn der Burg muss unbestimmt bleiben, aber mit Ulricus de Reichenstein tritt 1230 die Veste erstmals in die urkundliche Geschichte ein.

Ab 1264 findet sich ein Poppo de Reichenstein und später sein Sohn Hugo in den Quellen.

1295 verleiht Herzog Albrecht I. die Hälfte der Burg an Chunrad von Capellen. Nach

1326 befand sich die zweite Hälfte im Besitz von Eberhard von Wallsee, der sie 1352 an Ulrich II. von Capellen weiterverkaufte. Ulrich hat sich aber wohl kaum längere Zeit hier aufgehalten, denn seine Hauptwohnsitze waren schon damals das nahegelegene Steyregg sowie das repräsentativ ausgebaute Ruttenstein. Im Laufe des 14. Jh. erfolgten etappenweise Um- und Ausbauten, bei denen bis auf wenige Teile fast die ganze alte Burg abgetragen bzw. überbaut wurde. Sichtlich wollte man damit einem erhöhten Platzbedarf und dem Wunsch nach mehr Wohnkomfort Rechnung tragen. Reichenstein entwickelte sich so zu einer beeindruckenden Adelsburg mit Ringmauer, Vorburg mit Burgkapelle und einem gewaltigen vierstöckigen Wohnbau mit herrschaftlicher Ausstattung.

1406 erlosch der männliche Stamm der Capeller und die Burg gelangte durch Heirat an Hartneid von Liechtenstein.

1567 erwarb der steirische Ritter Christoph Haym die Festung. Er und sein Sohn Hanns bauten sie zu einem prächtigen Renaissanceschloss um, dessen Festsäle mit prunkvollen Wandmalereien ausgestattet wurden. Hierzu wurden den evangelischen Untertanen so hohe Abgaben abgepresst, dass es zur Ermordung des verhassten katholischen Christoph Hayms im Jahre 1571 führte. Als Täter kam der protestantische Bauernführer Gaisrucker in Frage.

1616 starb Freiherr Hanns von Haym, und über seine Tochter Maria Johanna gelangte

1632 Reichenstein an Graf Wenzel Reichard von Sprinzenstein.

1729 kaufte Graf Gundaker Thomas von Starhemberg die Herrschaft, dessen Nachfahren noch heute Besitzer der Burgruine sind.

Gepachtet wird sie von einem Verein, der sich unter anderem um die Renovierung und die Organisation kultureller Veranstaltungen kümmert.