Oswald von Heimenhofen errichtete um etwa 1365 auf einer Felskuppe am Hang bei Walten einen halbrunden Wohnturm mit einem geräumigen, westlich gelegenen Anbau. Weitere Erwerbungen von Gütern stürzten die Heimenhofener jedoch bald in die Schuldenfalle. 1440 veräußerte Erkinger von Heimenhofen seinen Anteil der Burg an den Bischof von Augsburg.

1444 kommt es durch die Heimenhofener zum Totschlag eines Leibeigenen des Bischofs von Augsburg. Bald treffen die augsburgischen Truppen vor Fluhenstein ein und zwingen Ulrich von Heimenhofen zur Aufgabe. Ulrich wird nach Füssen in Arrest geführt.

1462 kommt es zum Streit zwischen den Heimenhofenern und der Reichsstadt Kempten, da Ulrich der Jüngere von Heimenhofen Teile der Stadt unter seine Gerichtsbarkeit zwingen will. Im darauf folgenden Jahr stellen sich auch das Bistum Augsburg, sowie Graf Hugo von Montfort zu Rothenfels an die Seite der Reichsstadt Kempten und besetzen Fluhenstein. Diesmal kam der streitbare Burgherr in Kempten in Gefangenschaft.

Um 1508 schließlich verloren die Heimenhofener all ihre Besitzungen. Amtsleute des Bistums Augsburg verwalteten die Herrschaft Fluhenstein.

1525 wird die Burg im Zuge des Deutschen Bauernkrieges von Aufständischen geplündert und 1546 besetzten Truppen des Schwäbischen Bundes die Festung. Während des Allgäuer Bauernaufstands 1607 zogen schließlich die revoltierenden Rettenberger Bauern vor die Burg und drangsalierten die Verteidiger. Im Verlauf des Dreißigjährigen Krieges kommt es abermals zur Plünderung von Fluhenstein durch die Schweden, anschließend wird nach umfangreichen Instandsetzungsarbeiten in der Veste der Amtssitz des Ammanns eingerichtet. Die Nutzung als solcher wird bis 1769 fortgesetzt, danach wird das in Sonthofen errichtete Pfleghaus als neuer Amtssitz bezogen.

Die Burg wird im Anschluss dem Verfall preisgegeben und 1808 an einen Bauern verkauft.