Möglicherweise geht die Burg Wolkenberg bereits auf das 12. Jahrhundert zurück. Eine sichere Nennung erfährt der Bau im Jahr 1262, als Albert von Wolkenberg bei Konradin von Schwaben in Konstanz weilt. 1344 kommt es zu einem folgenschweren Zwischenfall, als Ritter Konrad einen Bürger der Stadt Kempten erschlägt. Daraufhin erstürmen die Kemptener die Burg und nehmen den 'Landfriedensbrecher' gefangen und enthaupten ihn anschließend.

1398 wird die Herrschaft Wolkenberg in das stiftkemptische Gebiet einverleibt. Ab 1417 sitzt ein Vogt auf der Burg und verwaltet einen Teil des Stiftslandes im Auftrag des Abtes. 1460 wird der Vater des Kellermeisters Jörg Beck auf der Burg inhaftiert. Am 17. März führt der junge Beck die angeheuerten Appenzeller wegen des Streits mit dem Fürstabt von Kempten in die Schlacht auf dem Buchenberg. Der damalige Stiftsvogt Walther von Hohenegg kommt dabei ums Leben.

Am 4. April 1525 erobern Bauern von Leubas die Burg und brennen sie nieder. Es folgt ein Wiederaufbau, welcher wohl um 1557 abgeschlossen wurde. 1632 aber ereilt die Burg das selbe Schicksal noch einmal, als Bürger und Bauern des Stiftslandes Wolkenberg plündern und im Anschluss niederbrennen. Es folgen danach nur noch notdürftige Instandsetzungen, gegen Ende des 17. Jahrhunderts wird das noch vorhandene Gemäuer dann endgültig dem Verfall preisgegeben.