Burg Sterrenberg ist älter als die benachbarte Burg Liebenstein. Die Reichsburg wurde vermutlich schon vor dem Jahr 1100 in salischer Zeit als Reichsburg erbaut und zählt damit zu einer der ältesten Höhenburgen am Rhein (angeblich 1034 erstmals erwähnt). Der Bauplatz am Ende eines langgezogenen Bergsporns über dem Bornhofer Bach ist so gewählt, dass die Burg ein langes Verteidigungsvorfeld besitzt und der Rhein berg- und talwärts gut überblickt werden kann. Die Burg sicherte den rechtsrheinischen Teil des "Bopparder Reiches", eines dem Königtum militärisch und wirtschaftlich direkt unterstellten Reichsgutbezirkes.
Mit ihrer Verwaltung wurde vor 1194/1198 die Reichsministerialenfamilie von Bolanden betraut, die auch den Bopparder Zoll verwaltete. Der Reichsministeriale Werner II. von Bolanden zählte Burg Sterrenberg in seinem damals abgefassten Lehnsbuch unter denjenigen Burgen auf, die er von Kaiser und Reich zu Lehen trug. Im Jahr 1268 wurde Sterrenberg unter den Brüdern Werner und Philipp von Bolanden aufgeteilt.
1286 versuchte Werner von Bolanden, die Teilung von 1268 rückgängig zu machen, dies wurde jedoch im Jahr 1288 vom Vormund des Nachfolgers von Philipp von Bolanden abgelehnt. Als der Nachfolger Philipps in jungen Jahren verstarb, ging sein erblich zugestandener Burgteil an seine beiden Schwestern über. Albrecht von Lewenstein, der Ehemann einer dieser Schwestern, ließ in den Jahren 1284 bis 1290 unweit von Sterrenberg Burg Liebenstein erbauen.
Im Jahr 1295 fiel Sterrenberg für kurze Zeit in die Verfügungsgewalt der Grafen von Sponheim-Dannenfels.
In den Jahren 1315 bis 1320 wurde die Burg Sterrenberg vom Trierer Erzbischof Balduin von Luxemburg (1285-1354) als Bestandteil seines "Bopparder Reiches" erworben. Die Herren von Bolanden verlegten ihren Sitz auf die benachbarte Burg Liebenstein. Sterrenberg wird zu einem Mittelpunkt der Verwaltung des kurtrierischen Amtes Sterrenberg-Hirzenach. Unter Heinrich Beyer von Boppard, offiziell Burgmann, wird die Burg 1340 ausgebaut, sein Nachfolger Lamprecht von Schonenburg nennt sich 1352 „Graf von Sterrenberg“. Die Trierer ließen Ende des 14. Jahrhunderts die sagenumwobene Zwischenmauer gegen Burg Liebenstein errichten. Die volkstümliche Sage von den "feindlichen Brüdern" geht möglicherweise auf das Spannungsverhältnis zwischen Liebenstein und dem trierisch gewordenen Sterrenberg zurück.
Sterrenberg war bis 1492 Sitz eines Kurtrierer Amtes, wurde aber bereits 1568 in einem Vertrag zwischen Philipp von Nassau und Erzbischof Jakob III. von Eltz als „arg zerfallen und unbewohnt“ bezeichnet. 1806 kam die Burgruine in nassauischen, 1866 in preußischen Besitz und schließlich im Jahr 1946 an das Land Rheinland-Pfalz.
Daraufhin leitete man 1968 umfangreiche Ausbau- und Instandsetzungsarbeiten ein, die der Burg Sterrenberg wieder ein mittelalterliches Erscheinungsbild gaben. 1774 wurde der quadratische Bergfried wieder zu seiner ursprünglichen Höhe aufgemauert.