Unmittelbar nachdem der Bayernherzog Heinrich der Zänker die Ungarn 991 besiegt und das Umland von Wien wie auch den Raum des Alpenostrandes besetzt hatte, errichtete ein babenbergischer Dienstmann, wahrscheinlich mit Namen Berchtold, auf dem Hügel über dem heutigen Marktplatz eine Turmburg aus Stein und umgab sie mit Wall und Graben sowie einem Palisadenzaun. Diese erste Burg war Glied einer Befestigungskette, die um die Jahrtausendwende an der südlichen Abdachung des Wienerwaldes zur Abwehr gegen Einfälle aus dem Osten entstand. Um 1180 wurde der Bergfried erbaut, der heutige Südturm der Burg.

Wer der namensstiftende Berchtold war, entzieht sich unserer Kenntnis, wir wissen nur, dass er der Ahne des einflussreichen und machtbewussten Landherrengeschlechts derer von Perchtoldsdorf gewesen ist.
Die Familie der Herren von Perchtoldsdorf entwickelte sich unter den Babenbergern zu einem der bedeutendsten Geschlechter des Herzogtums. Otto I. von Perchtoldsdorf besaß seine Herrschaft als freies Eigen. Er übergab sie 1232 dem Kloster Melk und nahm sie wieder als Lehen zurück. 1236 beteiligte er sich am Adelsaufstand gegen Herzog Friedrich II. den Streitbaren. Das Ergebnis war, dass dieser im Oktober des gleichen Jahres im Zuge eines Angriffs die Turmburg zerstören ließ. Im dritten Viertel des 13. Jahrhunderts ließ Otto II., der in der Gunst des Landesfürsten stand und es bis zum Kämmerer von Österreich brachte, die Befestigungsanlagen erneuern und vergrößern: Um 1250/70 entstanden Palas und Wohntrakt (dreigeschossig) in reinem Quadermauerwerk sowie ein Torturm mit Zugbrücke.
Auch Otto III. beteiligte sich an einem Adelsaufstand gegen den Landesherrn. Herzog Albrecht I. ließ 1290 in einer Strafexpedition die Perchtoldsdorfer Burg niederbrennen, Otto selbst wurde gefangen genommen und verstarb vermutlich im Gefängnis. Mit dem Tod seines Bruders Heinrich IV. starben die Herren von Perchtoldsdorf 1308 aus.

Herzog Albrecht I. hatte die Oberhand behalten, war seit 1298 römisch-deutscher König und zog die Herrschaft Perchtoldsdorf, das ehemalige Eigentum der Herren von Perchtoldsdorf, als „erledigtes Lehen“ ein. Albrecht I. fiel am 1. Mai 1308 einem Mordanschlag zum Opfer.

Sein Sohn und Nachfolger Friedrich der Schöne, zum Todeszeitpunkt seines Vaters gerade 19 Jahre alt, hatte ein schwieriges Erbe anzutreten. Um seine Ansprüche zu behaupten, war er selbst zum Kriegführen gezwungen und benötigte daher umgehend beträchtliche finanzielle Mittel, die nur durch Verpfändungen größeren Umfanges aufgebracht werden konnten. Um den Überblick über die Transaktionen zu bewahren, ließ er um 1313 ein „Pfandschaftsregister“ anlegen, dem die Information zu entnehmen ist, dass er am 27. Mai 1308, also keine vier Wochen nach dem Tod seines Vaters, „castrum et forum“, Burg und Markt Perchtoldsdorf, an das vermögende Adelsgeschlecht der Herren von Gerlos um eine nicht genannte Summe verpfändet hatte.
Wie lange die Phase der Verpfändung gedauert hat, lässt sich heute nicht mehr mit Sicherheit angeben, die wirtschaftliche Entwicklung des Ortes konnte sie nicht aufhalten. Die Habsburger fanden zunehmend Gefallen am Ort, bauten ihn in den Jahren bis 1338 weiter aus, bis er schließlich ab der zweiten Hälfte des 14. Jahrhunderts den Status einer landesfürstlichen Nebenresidenz einnehmen konnte und in der Burg zu Perchtoldsdorf die habsburgischen Herzoginnen residierten. 
Erste Grundherrin war Elisabeth I. von Görz und Tirol, (Witwe nach Albrecht I.), die bereits den Plan fasste, in Perchtoldsdorf ein Spital zu errichten. Danach gehörte das Lehen Elisabeth von Virneburg, der Witwe Herzog Heinrichs († 1327) bis zu ihrem Tod 1343. Als nächste kam Johanna von Pfirt (Gattin Herzog Albrechts II) bis 1351 in den Besitz von Burg und Markt Perchtoldsdorf, ihr folgte Katharina von Luxemburg (sie war in erster Ehe mit Rudolf IV. dem Stifter, vermählt).
Die bedeutendste war aber Beatrix von Zollern († 1419), Witwe Herzog Albrechts III., die zwischen 1395 und 1414 viele Jahre in Perchtoldsdorf verbrachte. Wohl residierten die Herzoginnen zumeist nicht ständig in Perchtoldsdorf, doch im Sog der herrschaftlichen Hofhaltung nahmen Weinbau- und Weinhandel einen beachtlichen Aufschwung und verhalfen den Ortsbewohnern zu einigem Wohlstand.

Dem ersten Türkensturm 1529 konnte die Burg, die damals ihre größte Ausdehnung erreicht hatte, standhalten. Im Zuge der 2. Türkenbelagerung jedoch wurde sie zerstört und nicht wieder aufgebaut. Erst in den Jahren 1964 - 67 nahm sich die Marktgemeinde des halb verfallenen Gebäudes an und baute es zu einem Veranstaltungszentrum aus.

Dem ersten Türkensturm 1529 konnte die Burg, die damals ihre größte Ausdehnung erreicht hatte, standhalten. Im Zuge der 2. Türkenbelagerung jedoch wurde sie zerstört und nicht wieder aufgebaut.

Erst in den Jahren 1964 - 67 nahm sich die Marktgemeinde des halb verfallenen Gebäudes an. Seit ihrer Revitalisierung vor mehr als 40 Jahren wird die Burg für Veranstaltungszwecke genutzt.