Der Name Fleckenstein erscheint im XII. Jh., für die einen 1129, für andere genau am 22. August 1174. Da befand sich nämlich in Gefolge des Kaisers Barbarossa ein Reichsministerialer namens Gottfried von Fleckenstein.
Im Laufe der Zeit wurden die Fleckenstein zu der bedeutendsten Adelsfamilie des nördlichen Elsass und besassen zahlreiche Güter und Rechte auf viele Dörfer der Gegend. Sie waren ursprünglich in drei Stämme gegliedert, bereits Anfang des XIV. Jh. allerdings nur noch in zwei. Beide Linien hielten daran, die Stammburg gemeinsam zu verwalten. Die Burg wurde dann in ein “Hinterhaus” und in ein “Vorderhaus” getrennt.
Die Burgfrieden aus den Jahren 1408, 1542, 1547 und 1551 liefern uns wesentliche Nachrichten über die Entwicklung der Burg , während die Kopie eines Wandteppichs aus dem Jahre 1562 ein sehr glaubwürdiges Bild des Zustands der Burg im späten Mittelalter widergibt. Zerstört wurde sie durch die Truppen des Königs Ludwig XIV., vermutlich 1689. Wenige Jahrzehnte später (1720) erlosch der letzte Fleckensteiner. Bis etwa 1890 liegt die Burg im Dornröschenschlaf. Zu dieser Zeit liess der Kreisdirektor von Weissenburg einige Mauerarbeiten durchführen. 1898 kam sie unter Denkmalschutz, eine Massnahme, welche 1933 durch den französischen Staat bestätigt wurde. 1958 wurde sie dem Fremdenverkehr erschlossen, blieb jedoch in Privatbesitz. 1998 erwarb die Gemeinde Lembach den umliegenden Wald, somit wurde die Burg Gemeindegut.
