Hrad pravděpodobně vznikl v první polovině 14. století. Za jeho stavebníka se předpokládá Bušek II. z Velhartic. Podle názoru J. Jánského však o Novém Herštejně psal již Protivec z Herštejna v roce 1272. Tento předpoklad podporují i výsledky posledního archeologického výzkumu hradu Nového Herštejna, jehož nejstarší stavební etapa mohla vzniknout již v poslední třetině 13. století.
Hrad zůstával podstatnou část doby existence v držení pánů z Velhartic. V pohraniční válce s Bavory byl roku 1475 dobyt, vypálen a pobořen. V roce 1496 ho za koupil Půta Švihovský z Rýzmberka, který ho pravděpodobně obnovil. V roce 1508 jeho syn získal i sousední hrad Rýzmberk. V roce 1512 byl hrad přestavován (vznikla zde stáj pro 200 koní a jiné stavební úpravy), což nepochybně souviselo s letitou záští Rýzmberků s Horní Falcí. Význam ztratil po roce 1524, kdy byl prodán Domažlickým a následně zpustl.

Dispozice je dvojdílná a vykazuje složitější stavební vývoj. V čele podélného jádra stál ohromný čtyřhranný nejméně třípatrový plochostropý donjon o rozměrech 16,6 x 15,6 metru. Podle vyobrazení na mapě z roku 1514 ukončený podsebitím s nárožními vížkami a krytý vysokou střechou. Zbytek plochy jádra nevykazuje žádné nadzemní zbytky staveb. Jádro stojí zhruba ve středu rozsáhlého vnějšího ohrazení trojúhelného obrysu s jednou zalomenou stranou. Jeho hradby byly v další stavební fázi navýšeny. Na západě s k hradbě přikládá čtyřhranná věž, další pravděpodobně stála v jižním nároží. K hradbě byly zevnitř přistavěny hospodářské a provozní budovy. Vstup umožňovala čtyřhranná věžovitá brána v severovýchodním nároží. Přístupová cesta k hradu vedla po celou východní frontu hradu, kde ji přepažovala první brána. Zde byl připojen k vnějšímu opevnění zvenčí objekt ke starší polookrouhlé baště, zpevněný polookrouhlou věžicí, zvaný Panenská bašta určená k obraně brány. Ostatní strany hradu obíhá příkop, před ním byl mohutný val. Na přístupu k hradu jsou patrné pozůstatky terénních úprav, které pravděpodobně pocházejí se zemními fortifikacemi z nejmladší fáze stavby hradu. Dochované konstrukce hradu lze klást do první poloviny 14. století. Starší fáze zůstává prozatím neznámá. V pohraničních válkách v 15. století a na počátku 16. století bylo nutno zvýšit obranyschopnost hradu zvýšením a posílením vnějšího opevnění. Stavební materiál pro tyto práce byl získán rozebráním jádra hradu, z něhož zůstala zachována pouze velká věž. Obvodové hradby vykazují stopy záměrného boření.

Zatímco starší badatelé, především August Sedláček, předpokládali, že rodovým hradem tohoto šlechtického rodu byl pravděpodobně hrad Starý Herštejn na Poběžovicku, přišel historik Jiří Jánský s myšlenkou spojit jeho členy s počátky hradu Nového Herštejna u Kdyně.  Prvním známým vlastníkem Herštejna byl v roce 1272 Protivec, bratr župana Vitly ze Staňkova.