The importance of the castle and its location are already dating back to prehistoric times: Thousands of years ago, the present location was the site of a prehistoric hillfort. According to research, the first medieval castle has presumably been constructed at the beginning of the 12th century. The old name "Grizanstein", from which the present name Kreuzenstein (= cross stone) emerged, was first mentioned around 1115 and can likely be traced back to one of the castle’s first lords and owners, Dietrich of Grizanestaine from the Bavarian Formbacher family. Other assumptions about the name’s origin mention a fortress lord called " Grizzo " or the cross of St. Severin, making even the castle’s name itself a fabled legend.
By marriage, Dietrich of Grizanestaine’s son-in-law Engelbrecht of Wasserburg became the new lord of Kreuzenstein, whose descendants owned the castle for over a century. During the middle of the 13th century, Kreuzenstein came into the possession of the Habsburg family who had the castle mostly maintained by caretakers and castellans by more than 250 years. The castle’s history was particularly erratic during the 16th and 17th century, with frequently changing owners, among others the Bohemian King George of Podiebrad (whose troops were commanded by Wenzel Wilczek, an ancestor of the present owner), Count Ferdinand of Hardegg, Baron Johann of Herberstein and Count Charles of Saint-Hilaire, who had the military facilities of the castle converted to one of the most powerful strongholds at the gates of Vienna the during the Thirty Years' War.
Probably the darkest hour in the history of Kreuzenstein came in 1645 during the final years of the Thirty Years' War: overwhelmed by the superior power of the Swedish army laying siege to Vienna, Colonel Luckas Spicker, the Imperial governor of Kreuzenstein and Korneuburg, surrendered the castle without resistance to Swedish Field Marshal Count Lennart Torstensson, who opened his headquarters here. Forced back by Austrian Archduke Leopold Wilhelm's troops, the castle was soon abandoned by the Swedes and largely destroyed by demolition charges during the retreat. During the following decades, the ruin’s remains were used by the surrounding inhabitants as a quarry for construction materials so that soon only sparse remains were left such as part of the curtain wall, the foundations and stub of the east tower and parts of the chapel.
Already in 1702, the ruins of Kreuzenstein had come into the possession of the later Imperial Count and Field Marshall Heinrich Wilhelm von Wilczek, by marriage to the last daughter of the house of Saint-Hilaire. But it was not until more than 170 years later that his descendant Johann Nepomuk Graf Wilczek, an important figure of the Austrian art and cultural life as well as a great patron of science and non-profit organizations, began the reconstruction of Kreuzenstein in 1874 and transformed the castle into the extraordinary and unique museum of the Middle Ages that it is today.