Wie bei vielen anderen Burgen des Hunsrücks lassen sich die Anfänge von Burg Stromberg nur mit großen Lücken zurückverfolgen. Ein Graf Bertolt von Stromberg, der 1090 erwähnt wird (eine bisher stets als Erstbeleg angeführte Nennung Bertolds zu 1056 beruht auf einer Fälschung), könnte seinen Namen von Stromberg abgeleitet haben, jedoch ist dies kein Beweis für die Existenz einer Wehranlage. Erst im Verlauf der Auseinandersetzungen zwischen Kaiser Heinrich V. und Erzbischof Adalbert 1. von Mainz tritt eine Burg in Stromberg eindeutig hervor. Heinrich hatte Adalbert wegen territorialer Interessen nach mehr als zwei Jahren Haft 1115 freigelassen, woraufhin der Mainzer Erzbischof den Konflikt fortsetzte und 1116, wie der Kaiser in einem Brief an die Mainzer Bürger zornig formulierte, „unsere Burg Stromberg völlig zerstört“ hatte. Schenkt man dem archäologischen Befund Glauben, dann ist sie mit der nach 1984 ergrabenen Burg auf dem Pfarrköpfchen identisch, die somit die Vorgöngeranlage der heutigen Stromburg wäre. Deren erste sichere Erwähnung geht in das Jahr 1242 zurück, als Berlewin Zurno, Marschall Pfalzgraf Ottos II., in Castro Starkenburg eine Urkunde ausstellte. Hier wie auch in späteren Zeiten zeigt sich, dass die rheinischen Pfalzgrafen Eigentümer der Anlage waren. Von einem bis heute behaupteten Übergang der alten Reichsburg mit dem Amtsantritt Pfalzgraf Konrads von Staufen 1156 kann angesichts fehlender archäologischer und schriftlicher Quellen keine Rede sein. Zahlreiche, seit 1250 nachgewiesene Burgmannen machen die Bedeutung der Anlage für die Pfalzgrafen in der Folgezeit deutlich. Mit den Pfalzgrafen am Rhein und ihren Nachfolgern, den Kurfürsten von der Pfalz, teilte die Stromburg auch deren wechselvolle Geschichte bis zur Zerstörung 1689 im Orléanschen Erbfolgekrieg des französischen Königs Ludwig XIV. mit der Kurpfalz durch französische Truppen.