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 in in die erste Hälfte des 12. Jahrhunderts fallen, 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 Leopold 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 Kapeller 1406 in deren Besitz. Die Pfandherrschaft Ruttenstein erwarben dann 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 und 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 musste 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.

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

Ruttenstein war bereits 1551 baufällig

• 1585: Ruttenstein ist zum Großteil schon eine Ruine
• 1594: Ein Brand richtet großen Schaden an
• 1727: Ein Blitzschlag zerstört weitere Teile der Ruine
• 1964: Erste Erhaltungsmaßnahmen finden statt (Holzstiege im romanischen Hochturm)
• 1968: Rundstiege vor dem Wohnturm wird restauriert
• 2002: Der Ruttensteiner Erhaltungsverein übernimmt die Sanierung der Ruine.

Heute wird die Ruine, welche in 750 m Seehöhe liegt, vom Ruttensteiner Erhaltungsverein gepflegt und betreut.