Aus historischen Quellen geht hervor, dass die Burg bereits 1160 als „castrum Rotenstein" mit bambergischem Besitz erwähnt wurde. Urkundlich wird sie jedoch erst 1209, in einer von Herzog Leopold für das Kloster Baumgartenberg ausgestellten Urkunde, unter dem Namen Rotenstein erwähnt.

Der Baubestand der Hochburg deutet jedoch auch darauf hin, dass die Burg wesentlich älter ist.
Die Bauzeit wird wohl ins 12. Jhdt fallen - möglicherweise in die erste Hälfte des 12. Jhts, was aber urkundlich nicht gesichert ist. Sie ist wohl eine Gründung des Grafen von Clam-Velburg, der Nachkommen der Herren von Machland um 1210 herum.

Nach dem Tod des Grafen Ulrich Clam-Velburg als Kreuzfahrer fiel dessen Besitz im Jahre 1217 an den Landesfürsten, dem Babenbergerherzog Albrecht VI.
Am 2. Mai 1281 verpfändete sie der neue Landesfürst, König Rudolf I. von Habsburg, Ulrich von Kapellen und sie verblieb bis zum Aussterben der Kapellen 1406 in deren Besitz. Die Pfandherrschaft Ruttenstein erbten die Wallseer.

Mit dem Erlöschen dieses Geschlechts im Jahre 1483 kamen die Liechtensteiner in den Pfandbesitz von Ruttenstein.
Als weitere Besitzer folgten 1492 Heinrich und Siegmund Prueschenk, 1493 lösten die Liechtensteiner Ruttenstein von den Prueschenken ein. Während dieser Zeit wird die Burg kaum oder nur kurz als Herrensitz gedient haben. Stattdessen wurde sie als wehrhafte Grenzburg von Burghauptleuten und Pflegern besetzt und verwaltet.

Schon 1492 mußte Christoph von Liechtenstein dem Kaiser die einstige Rodungsburg, die er nach den Grafen Clam-Velburg, den Kapellern und Wallseern erhalten hatte, zusammen mit Waxenberg und Wesenstein ausliefern. Das Haus Liechtenstein sollte dafür büßen, das es sich an die Seite des Matthias Corvinus, des Ungarnkönigs, gestellt hatte. Der Chronist der Familie Liechtenstein weiß zu berichten, daß sich dann 50 Jahre nach der Rückgabe der Herrschaft Ruttenstein, zu der die Märkte Weißenbach und Königswiesen gehörten, neuerlich ein Streit zwischen Habsburg und Liechtenstein um den begehrten Sitz entspann. Er endete, als der Landesfürst Ruttenstein endgültig für eine geringe Summe ankaufte.

Ruttenstein kam 1709 an Franz Ferdinand von Salburg, der die Herrschaft mit Schloss Aich, Zellhof und Prandegg vereinte.
Durch einen Blitzschlag wurde die Ruine 1727 arg in Mitleidenschaft gezogen.

Seit 1823 sind die Herzoge von Sachsen-Coburg-Gotha Eigentümer der Herrschaft Greinburg, zu der Ruttenstein auch heute noch gehört.

Die Ruine in 750 m Seehöhe ist heute fachmännisch abgesichert und betreut. Auf der höchsten Stelle der Waldkuppe stand die Altburg des 12. Jh., wahrscheinlich nur der jetzt zum Teil eingestürzte Wohnturm mit romanischer Tür und spitzbogigen Zwillingsfenstern, ebenso der fünfeckige Bergfried mit Stiegen im Mauerwerk, runden Fenstern und einer mannshohen Ringmauer.

Erst im 13./14. Jh. sind der Palas, Kapelle und Schildmauer entstanden. Im 15. Jh. legte man um diese Hauptburg eine riesige Vorburg mit sieben Rund- bzw. Schalentürmen.

Ruttenstein verfiel im 17. Jh., als der Besitz mit der Greinburg vereinigt wurde.