Die Burg Nové Hrady wurde wahrscheinlich in der ersten Hälfte des 13. Jahrhunderts auf einer Landzunge gebaut, die von dem Flüsschen Stropnice (dt. Strobnitz) und Novohradský potok (dt. Gratzenbach) umströmt wird. Die erste schrifltiche Erwähnung stammt aus dem Jahre 1279, als die Burg in den Besitz des Witigonen Ojíř überging. Im Jahre 1358 kaufen die Brüder Jan, Peter, Jost und Ulrich von Rosenberg das Gut. Von ihnen hielt sich hier nur Ulrich Längere Zeit auf. Die weiteren Rosenbergs bewohnten die Burg größtenteils nur zeitweise.

Die Burg diente dann als Zentrum des Gratzener Herrschaftsguts, welches zu den größten Besitztümern der Rosenberges gehörte und auch als wichtiger Militärstützpunkt. Im Verlauf der Hussitenkrige wurde die Burg von dem Hauptmann Jan aus Tábor, genannt Bzdinka, niedergebrannt. Im Jahr 1573 verpuffte bei einem Sturm durch einen Blitz das Schießpulver, das im gewaltigen, zylinderförmigen Turm, der im östlichen Teil des Burghofs stand, gelagert war. Die darauf folgende Explosion sprengte den Turm und beschädigte auch die umstehenden Gebäude. Die Zerstörung vollendete im Jahre 1590 ein verhältnismäßig starkes Erdbeben. Die Burg wurde stark beschädigt und es wurde sogar ihr Abriss in Erwägung gezogen. Abgerissen wurden schließlich nur die Ruinen des mächtigen Bergfrieds und wahrscheinlich auch der unmittelbar angrenzende Palast. Der Rest des Burgareals wurde repariert und nach den Plänen des italienischen Architekten Antonio Canevalle neu befestigt. 

Mit dem Tod des letzten Rosenbergs Peter Wok im Jahr 1611 ging das Herrschaftsgut auf Grund des Erbvertrags in den Besitz der Herren von Schwamberg über. Peter von Schwamberg beteiligte sich aktiv an dem Ständeaufstand (1618-1620) auf der Seite der Stände, und daher wurde die Burg von kaiserlichen Generälen belagert: Im März 1619 zuerst durch General Dampierre, danach im Juni 1619 durch den General Buquoy, der die Burg auch eroberte. Mit Urkunde 6. Februar 1620 bekam Karl Bonaventure Graf von Buquoy vom Kaiser für seine Verdienste und als Tilgung der Schulden die Herrschaftsgüter Gratzen, Rosenberg und Libejowitz. Kurz darauf wurde Karl Bonaventure bei dem folgenden Zug nach Ungarn bei der Belagerung von Neuhäusel erchossen. Seine Frau Maria Magdalena de Biglia, die in Belgien lebte, setzte zunächst auf das Gratzener Herschaftsgut Verwalter ein, die Brüder Gerhadt und Filip von Stratten. Nachdem Sie sich von deren Unzuverlässigkeit überzeugt hatte, sidelte sie im Jahre 1623 dauerhaft nach Böhmen über. 

Auf dem Gratzener Platz ließ sie anstelle der Herrenhäuser eine gemütliche Residenz bauen, in die sie ihren Sitz im Jahr 1635 verlegte. Dort residierten die Buquoys bis zum Anfang des 19. Jahrhunderts, als ein neues Empire-Schloss auf der nördlichen Seite der Stadt gebaut wurde. Die Burg Nové Hrady verlor so definitiv ihre Funktion als Residenz und wurde in dieser Zeit zu Wohnzwecken der herrschaftlichen Beamten, als Waldverwaltung und zu weiteren wirtschaftlichen Zecken verwendet. 

Mit Ende des 18. Jahrhunderts wurde der obere Teil des nordöstlichen Turms angebaut, wo das Familienarchiv der Buquoys und die Bibliothek angelegt wurden. Am Ende des 2. Weltkriegs errichtete die rote Armee ihr Kommando auf der Burg und ein Teil der Archivalien wurde zerstört. Auf Grundlage der Beweise über die Kollaboration des letzten Eigentümers Karl Georg wurde den Buquoys das Herrschaftsgut konfisziert und in die Pflege des Staates übergeben. In den fünfziger Jahren des zwanzigsten Jahrhunderts wurde in Teilen der Burg eine Ausstellung eingerichtet, die überwiegend aus Haylithglas bestand, der Rest diente weiter als Wohnungen und später ein Teil auch als Volkschule der Künste und Kulturzentrum. In den achtziger Jahren wurde die Burg umfassend renoviert. Im Jahre 2000 wurde eine neue Ausstellung geschaffen und im Jahr 2002 ging die Burg in die Verwaltung des staatlichen Denkmalinstituts, heute Nationalinstitut für Denkmalpflege, über, welches sie heute bis jetzt verwaltet.