Die Geschichte von Landstein beginnt spätestens nach 1222, als der mährische Markgraf Vladislav gestorben war und der böhmische König Přemysl Otakar I. die Verwaltung übernahm. Mit der Absicht, eine sichere Landgrenze herzustellen, ließ er in den umstrittenen Gebieten Wachburgen errichten. Auf dem Landweg, direkt gegenüber der älteren, wohl gleichnamigen Burg der österreichischen Herren von Zöbing wurde die königliche Burg Landstein gegründet. Diese Burg bewachte nicht nur den Landweg, sondern auch einen Teil der Grenze zwischen den böhmischen Ländern und Österreich. Mitte des 13. Jahrhunderts erwarben die Wittigoner die Burg aus den Händen des Herrschers. Eine Linie dieser Familie mit dem Emblem der silbernen fünfblättrigen Rose auf rotem Grund übernahm nach der Burg das Prädikat   als Herren von Landstein und wurde sehr bald eine der mächtigsten Adelsfamilien im Königreich. Unter der Herrschaft von Wilhelm von Landstein gehörte der Familie neben Landstein auch Wittingau /Třeboň/, Lomnic /Lomnice/, Gratzen /Nové Hrady/, Schweinitz /Trhové Sviny/ und Forbes /Borovany/. Wegen seinen politischen Ambitionen geriet Wilhelm von Landstein mit dem König Johann von Luxemburg in Streit, der gegen den aufrührerischen Wittigoner mit der Armee zu Felde zog. Mit Hilfe seines Onkels Peter von Rosenberg zwang er das königliche Heer zum Rückzug und 1318 versöhnten sich die beiden Wittigoner schließlich mit dem König und wurden treue, mit nicht geringen Privilegien belohnte Bedienstete. König Karl IV. schätzte Wilhelm sehr, beauftrage ihn mit verschiedenen diplomatischen Aufgaben und ernannte Wilhelm 1351 zum Prager Burggraf. Der alte Landweg, der durch Landstein führte, brachte den Wittigonern großen Reichtum. Seit Anfang des 14. Jahrhunderts führten die Landsteiner einen Streit über die Richtung dieses Wegs mit ihren Nachbarn, den Herren von Neuhaus /von Hradec/. Der Streit erreichte um die Mitte des Jahrhunderts mit einem offenen Krieg zwischen Wilhelm und Heinrich von Neuhaus seinen Höhepunkt, als der den Landweg umleitete. Obwohl König Karl IV. den Streit mehrmals zu schlichten suchte, kulminierte die Feindschaft in einem Duell, wobei Wilhelm von Heinrich tödlich verletzt wurde. Einer der mächtigsten Männer des Königreiches starb im April 1356 auf Burg Landstein und mit dessen Tod fand die ruhmreichste Ära der Herren von Landstein ihr Ende.

1381 trat König Wenzel IV. die Burg Landstein an Konrad Krajger von Krajgk ab. Die ursprünglich österreichische Familie ist jedoch schnell in Böhmen heimisch geworden. Die Kraiger schlossen sich den Kriegen der Hussiten an und kämpften sogar auf beiden Seiten. Konrads Sohn Lipold kämpfte mit den Hussiten auf der katholischen Seite als Siegmunds Hauptmann von Budweis /Budějovice/ und als Vergeltung setzte Jan Žižka die Burg in Bistritz /Bystřice/ in Brand, nahm dessen Frau und Kinder gefangen und attackierte auch die Burg Landstein. Lipolds Sohn Wolfgang wiederum ging zu den Utraquisten. Die Familie der Kraiger brachte den komfortablen Lebensstil der Renaissance in die strenge mittelalterliche Burg. Die letzte Erbin des Geschlechts, Anna, vermählte Roupovská, verkaufte die Burg an den obersten erblichen Kammerherrn in Österreich, Stephan von Einzig. Die Burg wechselte schnell mehrere Besitzer, wurde dann nicht mehr ständig von der Herrschaft bewohnt und diente nur noch der Gutsverwaltung.

1771 schlug ein Blitz in den Turm ein und der dadurch verursachte Brand beschädigte die bewohnten Teile der Burg.  Die schnell baufällig gewordene verlassene Burg diente dann als Quelle für Baumaterial für die benachbarten Dörfer und schließlich auch als romantische Ruine, wohin der „Klub tschechischer Touristen“ Ausflüge veranstaltete.

1945 wurde die Burg verstaatlicht und 1948 erfolgte die Übergabe an die touristische Abteilung der Tschechoslowakischen Sokol-Gemeinde. 1954 übernahm der Staat die Verwaltung.

1972 begann die umfangreiche Sanierung des baufälligen Mauerwerks, um die Burg Landstein 1990 der Öffentlichkeit wieder zugänglich machen zu können.