Vznik hradu je v první polovině 14.století a to podle písemných zpráv do roku 1348. Pravděpodobně jej založil Bušek II. z Velhartic, který byl synem stejnojmenného komorníka markraběte Karla, který zamřel kolem roku 1337 v Meranu. Bušek II. hrál významnou roli na dvoře Karla IV.,jeho zástupci byli příbuzní Protiva a Břeněk z Herštejna, o kterých už máme výslovné zprávy, že vládli na Novém Herštejně v letech 1348-1349. Po Břeňkovi, který byl ve službách olomouckého biskupa a v roce 1355 byl patronem kostela v blízké Úboči, vládl na hradě Ješek z Velhartic, který byl v letech 1356-1367 maršálkem královského dvora.Brzy pomom zemřel a zanechal novoherštejnský statek vdově Ofce z Újezdce a mladičkému synu Janovi. Jan převzal statek od matky před rokem 1385, kdy se též dostal do sporů s pány z Rožmberka, kteří pravděpodobně Nový Herštejn dobyli a Jana z Velhartic zajali. Můžeme tak usuzovat podle zápisů z ledna 1385 v zemských deskách, v kterých se Jan zavazoval, že hrad bude kdykoli otevřen Oldřichovi z Rožmberka a jeho synu Jindřichovi a dočasně jim byl i zapsán do splacení 50 kop. Jan z Velhartic byl v letech 1397-1412 přísedícím zemského soudu. Na konci hustiské revoluce se dostal do sporu s bavorským knížetem Vilémem, ve kterém mu pomáhali katoličtí páni. V roce 1435 se Jan připomíná naposledy, hrad přešel do rukou jeho čtyř synů, z kterých Arnošt je v pramenech uváděn naposledy v roce 1465.

Někdy na konci vlády Jiřího z Poděbrad převzal Nový Herštejn syn jednoho ze zmíněných čtyř bratří, Jan Herštejnský z Velhartic, spolu s nejmenovaným bratrem. Patřil k nepokojným vladykům Plzeňského kraje, kteří se v roce 1473 dostali do sporů s bavorským knížetem Albrechtem. V říjnu 1474 přitáhlo bavorské vojsko až k Novému Herštejnu a Bavorům se podařilo zajmout jeho majitele, nevíme však, zda hrad dobyli. Po třech měsících uzavřel Bohuslav ze Švamberka a Dobrohost z Ronšperka s bavorským knížetem Albrechtem dvouměsíční příměří, ve kterém měl být Jan Herštejnský na svobodě, ale po jeho oplynutí se měl dostavit na bavorský hrad Straubing. Jan Herštejnský však začal plenit bavorské statky hned, jakmile byl propuštěn a proto Bavoři podnikli vojenskou výpravu proti němu. Někdy na počátku února 1475 přitáhli k Novému Herštejnu, hrad dobyli a Jana znovu zajali. Jednání z vítěznými Bavory se ujal prostřednictvím svých úředníků Zdeněk ze Šternberka, do kterých služeb se Jan Herštejnský původně dal najmout. Přestože Bavorům bylo slibováno, že útoky z Nového Herštejna přestanou a na tehdejších sněmech se s nimi jednalo o podepsání konečného míru. Bavoři nakonec podle příkazu knížete Albrechta hrad úplně vyvrátili a vypálili. Zdeněk ze Šternberka žádal, aby jeho služebník Jan Herštejnský byl z vězení propuštěn a byla mu nahrazena škoda za zničený hrad. Jan však byl propuštěn až v lednu 1476, když se uvolil zaplatit výkupné 1000 zlatých. Tuto velkou peněžní částku ze svého zoustlého statku zaplatit nemohl a tak došlo k novému nepřátelství s Bavory, které bylo ukončeno nějakou smlouvou v roce 1481, jejíž obsah neznáme. Náhradu za zničený hrad však Jan Herštejnský jistě nezískal, přestože o to usiloval ještě v roce 1496 a tak se uchýlil na nedaleký malý statek Lomec, kde se připomíná v letech 1509-1515.Jiné zprávy o něm nemáme a tak ani nevíme, zda se zpráva starého letopisce z roku 1520, že byl na Hradčanech za Daliborku sťat,nebo někdo z jeho synů.

Na přelomu 15. a 16.století koupil herštejnské zboží, pravděpodobně ještě od Jana Herštejnského z Velhartic, Půta Švihovský z Rýzmberka, který umírá roku 1504. Při dělení velkého Půtova majetku mezi pozůstalé syny připadl Nový Herštejn Břetislavovi. Za jeho vlády už za krátké vlády otcovy, došlo jen k nejnutnější opravě hradu, aby na něm mohl bydlet úředník, oprava je dodnes patrná na Panenské věži a na vyplňování zdiva cihlami.Pokles významu Nového Herštějna ovlivnila i skutečnost, že Břetislav v roce 1508 znovu získal pro svůj rod hrad Rýzmburk. Břetislav z Rýzmburka, který patřil mezi přední odpůrce volby Ferdinanda I. za českého krále, však začal brzy své zboží pro dluhy prodávat a v letech 1524-1534 přišla řada i na novoherštejnský statek, který po delším váhání koupilo za 2350 kop grošů českých královské město Domažlice, které bylo ve švamberské zástavě.teprve z této kupní smlouvy známe rozsah celého statku. Domažličtí se však o hrad nestarali a nechali jej zpustnout, dvůr a hospodářské stavení pod hradem rozprodali poddaným, jako pustý se hrad uvádí v roce 1549. Pro účast na stavovském odboji proti Ferdinandovi I. v roce 1547 však byly Domažlickým všechny statky zkonfiskovány.Přestože větší část jim byla v roce 1549 navrácena, někdejší novoherštejnský statek už nezískali, král Ferdinand I. jej v témže roce prodal za 900 kop grošů českých karlštejnskému purkrabímu Šebestiánovi Markvartovi z Hrádku. Vznikl tak staronový statek, který se ještě po celé 16.století nazýval herštejnský. Jeho držitelé však nesídlili na zpustlém hradě, ale na tvrzi v Únějovicích, kterou Domažličtí koupili v roce 1538. Mezi příslušenstvím únějovického statku se pustý Herštejn uvádí v roce 1626, kdy byly Únějovice připojeny k bystřickému panství.

Gotický hrad Nový Herštejn , vstupní věž, která už je zbořená, stála ve východním rohu nepravidelného troúhelníka. Nedaleko této věže byla ještě druhá brána, na které vybíhala z vlastního horního hradu, po bráně i hradbě zůstaly pouze hromady kamení.
Jádrem hradu byl čtyřhranný palác, který se rozkládal na jihovýchodě od okružní hradby a měl obvodní zeď 2 m silnou. Byl dvouposchoďový, snad i tříposchoďový a dodnes se z něho zachovalo poměrně velké množství zdí, mnohde až 10 m vysokých.V přízemí i prvním poschodí byly komory, bydlelo se ve druhém poschodí.
Dnes se můžete procházet po krásné zřícenině , která má své kouzlo.