Nový hrad byl postaven roku 1493 bratry Dobešem a Benešem Černohorskými z Boskovic, novými držiteli původního "Starého hradu", na původním místě jednoho ze šesti Uhry vybudovaných opevněných stanovišť sloužících k obléhání Starého hradu, který nakonec Uhři dobyli a rozbořili. K postavení Nového hradu byl použit materiál z rozbořeného Starého hradu (původně se jmenoval „Nový hrad“ a „Starým hradem“ začal být nazývám v lidovém podání po dokončení Nového hradu).
Nový hrad zůstával v držení rodu Černohorských z Boskovic i nadále. V roce 1562 vydal český král Ferdinand I. Habsburský rozhodnutí, že hrad, který dosud dávali králové do zástavy, Černohorským prodá. V roce 1597 vymřel rod po meči a panství vyženil Maxmilián z Lichtenštejna, který si vzal za manželku Kateřinu Černohorskou. Když v roce 1643 táhli kolem hradu poprvé Švédové, o dobytí hradu se ani nepokusili, ač ten skýtal množství majetku. Avšak roku 1645, kdy došlo ke švédskému obléhání Brna, byl hrad lstí přepaden a téměř bez boje obsazen. Podle pověsti nebyla hlídka hradu příliš obezřetná, v otevřené bráně hrála kostky, a tak měli Švédové usnadněnou úlohu. Jiná pověst vypráví o zradě olomučanského občana, který zradil ostrahu hradu a zavolal o otevření brány.
V roce 1655, v době tureckých nájezdů, byl hrad částečně opraven a koncem 17. století sloužil jako obydlí pro myslivce. V roce 1703 proběhla další oprava z důvodu hrozícího nebezpečí ze strany povstalců, byly zde skladovány i zbraně. V letech 1805-1807 došlo k romantické přestavbě hradu, byla postavena i vysoká věž. Když se však v letech 1843-1848 stavěla železniční dráha z Brna do České Třebové a razil se tunel, zvaný "novohradský," byla tato věž z důvodu obav, že se při otřesech z železniční trati zřítí, snížena. V roce 1920 se po první pozemkové reformě stal hrad majetkem státu. Přešel do vlastnictví Školního lesního podniku Křtiny a ještě v 50. letech 20. století zde byl výletní hostinec. Poté byl ponechán svému osudu a chátral. Počátkem 80. let se jeho záchrany ujali nadšenci, kteří hrad pod hlavičkou Českého svazu ochránců přírody převzali v roce 1990. Hrad je veřejnosti přístupný a konají se zde různé akce.
V roce 1994 se na hradě točil film V erbu lvice, dále pohádka O králi, hvězdáři, kejklíři a třech muzikantech z roku 1996 a v roce 2006 pohádka Tajemství Lesní země. V roce 2011 se pak natáčela pohádka Sněžný drak.