Die Burg Heidenreichstein ist die größte mittelalterliche Wasserburg Niederösterreichs. Ihre Gründung um 1180/90 wird einem gewissen "Heidenreich", Mitglied der Familie der Burggrafen von Gars zugeschrieben. Dieses Geschlecht gehörte zur landesfürstlichen Ministerialität und war stammesverwandt mit den Kuenringern. Die Burg liegt im Zentrum des Ortes in einer Niederung. 
Der architektonische Bestand ist stark spätgotisch und renaissancezeitlich geprägt und lässt abgesehen vom Bergfried kaum Hinweise auf einen hochmittelalterlichen Bestand erkennen. Der Bergfried besitzt eine Fülle ausgeprägter architektonischer Details, wie zum Beispiel ein die Geschoße verbindendes Stiegensystem, zwei übereinanderliegende Mantelkamine und Kreuzgratgewölbe. Er wird in die erste Hälfte des 13. Jahrhunderts datiert, wobei das oberste Geschoß mit umlaufendem Umgang aus dem 16. Jahrhundert stammt.
Ihr charakteristisches Aussehen erhält die Burg durch die drei die Ecken betonenden, unterschiedlich großen Rundtürme mit spitzen Kegeldächern und umlaufenden hölzernen Wehrgängen. Der nordöstliche Turm integriert die ehemalige Burgkapelle, deren flache Holzdecke noch spätgotische Rankenmalerei aufweist. Die Burg ist noch heute, mit Ausnahme der stadtseitigen Nordseite, von Wasser umgeben.