Zur Kontrolle des Verkehrs im Altmühl- und Schambachtal begann 1394 Herzog Stephan der Kneißel von Bayern-Ingolstadt im Gebiet des Hochstifts Eichstätt ohne Einwilligung des Bischofs die Feste „Neuenstein“ (Neu – im Gegensatz zum benachbarten älteren Arnsberg) zu errichten. Der Eichstätter Bischof Friedrich IV. Graf von Oettingen nahm aber diesen „Schwarzbau“ nicht hin, und Herzog Stephan der Kneißel mußte im Vertrag vom 8. Mai 1394 die begonnene Feste dem Hochstift übergeben.
Das weitere Schicksal der Burg liegt im Dunkeln, sie wurde wohl abgetragen oder dem Verfall preisgegeben. Der Volksmund formte den Namen „Neuenstein“ der in Vergessenheit geratenen Befestigung in „Nonnenstein“ um und verband damit die Sage, dass Nonnen aus dem 4 Kilometer entfernten Hofstetten ihre Spaziergänge bis an den Felsen ausgedehnt hätten.
Unmittelbar unter dem Nonnenstein am anderen Altmühlufer lag einst eine weitere Wehranlage; diese ehemalige Wasserburg, von der nur noch eine leichte Eintiefung den Verlauf des Grabens erahnen läßt, wird 1304 im Testament Gebhards, des letzten Grafen von Hirschberg, als „Rauhenwerde“ genannt und fiel nach dessen Tod 1305 an das Hochstift, das die Burg verfallen ließ.
