Das Alter von Burg Reichenstein lässt sich nicht auf das Jahr genau bestimmen. Doch deutet die Art der ältesten Gebäudeteile auf eine Entstehung der Burg im frühen 11. Jahrhundert hin: Reichenstein wäre damit fast 1000 Jahre alt. Damals gehörte die Gegend dem weit entfernten Kloster Kornelimünster bei Aachen, das sie bereits im 9. Jahrhundert von Ludwig dem Frommen geschenkt bekommen hatte und das zu Verwaltung und Wahrnehmung seiner Rechte Vögte einsetzte. Zu diesen Vögten gehörte zunächst der Ritter Rheinbodo (1151 - 1196) mit seinen Nachkommen. Einer von ihnen, Gerhard von Rheinbod, der auf Reichenstein residierte, wütete jedoch als Raubritter und verlangte den im Rheintal reisenden Kaufleuten sowie den Schiffern mit Gewalt ihre Ware ab. 1213 wurde er daher als Vogt abgesetzt. Aus jenem Jahr datiert auch die erste urkundliche Erwähnung der Burg. Sein Nachfolger wurde Ritter Philipp aus dem mächtigen Geschlecht von Bolanden. Sein Sohn Werner nahm 1218 den Namen "von Reichenstein" an, doch da er kinderlos starb, ging die Burg 1241 an einen Verwandten, Philipp von Hohenfels, über. Der Hohenfelser erwies sich als einer der schlimmsten Raubritter seiner Zeit, der den Anweisungen seiner Lehensherren in Kornelimünster in keiner Weise Folge leistete und auf immer neue Beute bei den durchs Rheintal ziehenden Händlern aus war.

253 setzte der Erzstift Mainz und das Heer des Rheinischen Städtebundes dem Rauben und Plündern Philipps ein vorläufiges Ende, indem sie Reichenstein eroberten und zerstörten. Philipp von Hohenfels hatte sich ergeben und Wohlverhalten gelobt, weshalb sein Leben geschont wurde. Doch nutzte er die anschließende Zeit, um Reichenstein stärker und wehrhafter als zuvor wieder aufzubauen. Er setzte sein Raubrittertum weiter fort, stieg in den politisch unstabilen Zeiten des sogenannten Interregnums (als verschiedene Herrscher um die deutsche Krone kämpften und sich in rascher Folge einander ablösten) sogar in das hohe Amt des Reichsvikars auf und vergriff sich auch an Kirchengut, weshalb er durch den Erzbischof von Mainz mit dem Kirchenbann belegt wurde. Als er 1277 starb, erbte sein Sohn Dietrich Burg Reichenstein, deren Lehensrechte mittlerweile vom fernen Kloster Kornelimünster auf den Erzstift Mainz übergangen waren. Dietrich von Hohenfels entwickelte sich in den folgenden Jahren zu einem Raubritter, der seinen berüchtigten Vater noch in den Schatten gestellt haben soll. Erst als mit der Wahl Rudolf von Habsburgs zum deutschen König das Interregnum beendet und die Reichsgewalt wieder gestärkt wurde, fand das Raubrittertum am Rhein (das keinesfalls nur auf Reichenstein beschränkt gewesen war) ein Ende.

1282 belagerte der neue König Burg Reichenstein. Zwar gelang es ihm nicht, die gut befestigte Anlage im Sturmangriff zu nehmen, doch konnte er die Besatzung durch Aushungern zur Aufgabe zwingen. Von der Härte der Kämpfe, die im 13. Jahrhundert um Reichenstein tobten, zeugen noch heute Pfeilspitzen, die immer wieder in der Umgebung der Burg gefunden wurden und von denen einige heute im Burgmuseum aufbewahrt werden. Während Dietrich von Hohenfels - entgegen der Sage - nicht enthauptet wurde, sondern entkam, wurden seine Spießgesellen auf Geheiß Rudolf von Habsburgs an den Bäumen im Tal aufgehängt, die Burg selbst wurde niedergebrannt. Doch obwohl der König noch 1290 den Wiederaufbau von Reichenstein und der benachbarten Burg Sooneck (zeitweilig ebenfalls ein gefürchtetes Robber-Knights Nest) ausdrücklich verboten hatte, waren beide kurz nach 1300 wieder neu entstanden. Zeitweilig war Reichenstein nun im Besitz der Pfalzgrafen, die sich mit den Erzbischöfen von Mainz um die Rechte an der Burg stritten. 1344 sprach Kaiser Ludwig IV. die Burg endgültig den Mainzern zu. Diese verpfändeten sie allerdings bis 1361 noch mehrmals, unter anderem an Kuno von Falkenstein, einen Nachkommen jener Herren Bolanden, die bereits knapp 150 Jahre vorher als Vögte auf Reichenstein gesessen hatten. Unruhige Zeiten kamen noch einmal 1396, als Gottfried von Leiningen, der Gegenbischof des vom Mainzer Domkapitel gewählten Erzbischofs Johann von Nassau, auf der Burg Zuflucht suchte und sie vom damaligen Burgvogt Nikolaus vom Stein auch gewährt bekam. Nur der nach langdauernden Verhandlungen schließlich erreichte freiwillige Rücktritt Gottfrieds verhinderte, daß es zu einer neuerlichen blutigen Schlacht um Reichenstein kam.