Burg und Name gehen auf den 1186 erstmals genannten Edelfreien Kuno von Stein zurück. Konstein war Lehen der Burggrafen von Nürnberg, die es 1408 an Bayern vertauschten. Leheninhaber waren bis um 1335 die Herren von Muhr, dann durch Heirat bis 1349 Ulrich Wilbrant, der 1345 von Kaiser Ludwig dem Bayern für die Burgsiedlung Stadt- und Marktrechte und 1347 die Hochgerichtsbarkeit erhielt. Wiederum durch Heirat war die Burg bis 1371 bzw. 1382 im Besitz der Schwäger Kuno von Laiming und Burkhard von Seckendorf und anschließend bis 1385 im Besitz des Eberhard Schenk von Roßberg, der die Veste an die Bayernherzöge verkaufte.
Diese verpfändeten sie 1388 gegen eine Pfandsumme von 3700 Gulden an die Hausner. Herzog Ludwig der Reiche löste 1457 Konstein aus der Verpfändung und ließ die Burg durch Pfleger verwalten. Im Landshuter Erbfolgekrieg wurde die Burg 1505 zerstört und danach Pfalz-Neuburg zugeteilt. 1506 - 1540 war sie an die Familie Pöll verliehen, die 1515 die Burg wieder aufbaute. Im Dreißigjährigen Krieg wurde die Burg wiederholt geplündert und unbewohnbar. 1795 wurde das Gut veräußert, das pfalz-neuburgische Pflegamt 1802 aufgelöst. Die Vorburg diente zu Beginn des 19. Jahrhunderts schließlich als Bräukeller.
