Burg Stadeck wurde wahrscheinlich Ende des 12. Jahrhunderts im Spannungsfeld zwischen den rheinischen Pfalzgrafen, den Herren von Sponheim und den Mainzer Erzbischöfen gegründet. Der eigentliche Bauherr ist unbekannt. Den Besitz der Burg teilten sich vermutlich die Grafen Leiningen und die Grafen von Katzenelnbogen, die ihren Anteil vielleicht als pfalzgräfliches Lehen trugen.

Erstmals genannt wird die Burg im Jahr 1276, als Dietrich von Hohenfels bei der Teilung der väterlichen Güter den sponmheimischen Teil der Burg erhielt.

In einer Notiz wird zum Jahr 1291 berichtet, dass Graf Eberhard I. von Katzenelnbogen Bauarbeiten an der Burg vornehmen ließ. Beleg für die wachsende Bedeutung der Burg und der Zuzug von Menschen in das Burgumfeld dürfte die Geschichte des Dorfes Hedesheim bei Stedecken sein, das nach und nach verlassen wurde und schließlich um 1325 weitgehend verlassen war.

Am 17. Januar 1301 erhielt Graf Eberhard für seinen Burgweiler durch König Albrecht I. Stadtrechte verliehen. Der Ort konnte sich aber nicht als städtisches Gemeinwesen entwickeln.