Die Festenburg scheint erst 1353 und damit relativ spät urkundlich auf. Sie dürfte aber bereits in der zweiten Hälfte des 13. Jahrhunderts von einem Gefolgsmann der Stubenberger gegründet worden sein.

Da keiner der Eigentümer hier ständig wohnte, wurde die Herrschaft von angestellten Burggrafen verwaltet. Im 14. Jahrhundert hatten Mitglieder der Familie Teufenbach mehrfach dieses Amt inne. Durch die Heirat einer Stubenbergerin mit Simon I von Mattersdorf-Forchtenstein war die Festenburg zu Beginn des 14. Jahrhunderts an dessen Familie gekommen. Die Burg war damals zweigeteilt. Niklas von Mattersdorf verkaufte 1353 die halbe Burg seinem Onkel Ulrich von Pergau als dessen freies Eigen, der 1355 auch die zweite Hälfte übernahm.

Dessen Tochter Sophie verkaufte 1366 die Herrschaft an die Brüder Leutold und Rudolf von Stadeck. Mit seinem gleichnamigen Enkel starb die Familie 1400 aus. Sowohl dessen Schwester Guta als auch seine Stiefmutter Anna heirateten in die Familie der Grafen von Montfort ein. 1416 erwarb Caspar von Saurau die Burg, während die Lehenshoheit aber bei den Grafen von Montfort verblieb. Damals existierten noch eine obere und eine untere Burg. Die obere wurde 1454 durch Brand zerstört, aber bald wieder aufgebaut. Um die Mitte des 16. Jahrhunderts hatte die Festenburg durch Erbteilung bereits mehrere Besitzer aus der Familie Saurau erhalten. Sie war zur Ganerbenburg geworden, da den Mitbesitzern einzelne Gebäude gehörten. Erst 1573 gelang es Sigmund von Saurau wieder den gesamten Besitz in seine Hand zu bringen. Bei den Saurauern blieb die Festenburg genau 200 Jahre lang.

Zur Zeit der Gegenreformation war der protestantische Andreas Sigmund von Saurau gezwungen, die Feste 1616 an das Stift Vorau zu verkaufen. Propst Daniel Gundau ließ den Ostteil der Burg zur Schlosskirche umbauen. Im etwas tiefer gelegenen Westteil wurde ein Wohntrakt errichtet. Zwischen 1707 und 1723 veranlasste Propst Philipp Leisl den Ausbau der Wohngebäude. Leisl ließ die Gebäude zum Teil in Kapellen und Kirchen verwandeln, wodurch die Festenburg ihr charakteristisches Aussehen erhielt. Nachdem die Festenburg zu Beginn des 19. Jahrhunderts bereits teilweise verfallen war, wurde sie anschließend wieder hergerichtet. Von 1889 bis zu seinem Tod im Jahr 1928 diente die Burg Dr. Ottokar Kernstock als Wohnsitz. 1892 wurde die Burg zur Pfarre erhoben. Sie befindet sich noch heute im Besitz des Stiftes Vorau und wird als Pfarrhof sowie für andere kirchliche und museale Zwecke genützt. Das 1988 begonnene umfangreiche Restaurierungsprogramm konnte vor wenigen Jahren abgeschlossen werden.

Weitere Informationen: Burgen Austria