Grad Fridrihštajn dao je početkom 15. stoljeća, između 1423. i 1425. godine, sagraditi sin celjskog grofa Hermana II., Friderik II., za svoju ljubavnicu Veroniku Desenišku, s kojom se nakon smrti svoje prve žene Elizabete Frankopanske i vjenčao.
Herman II. je dao utopiti Veroniku Desenišku nakon što je Celjski sud nije htio osuditi kao vješticu, a svojega je sina dao zatvoriti i grad srušiti. Nakon smrti svojega drugog sina Hermana III. pustio je Friderika na slobodu, a ovaj je potom dao obnoviti porušeni grad.
Nakon izumiranja dinastije grad je 1456. godine pripao habsburškom caru Fridriku III., koji ga je dao na upravljanje bivšem upravitelju Celjskog grada.
Kasnije je grad unajmio barun Jurij Thurn. On je 1515. znatno povisio poreze i time izazvao prvi slovenski seljački ustanak. Seljaci su u veljači iste godine ubili baruna Thurna. Udružene feudalne snage potom su ujesen iste godine ugušile pobunu i pogubile vođe ustanka.
Grad je potom gotovo netaknut stajao u zaklonu kočevskih šuma kao sjedište kočevskog vlastelinstva još jedno stoljeće. Godine 1641. grad je, zajedno s područjem na kojem se nalazio, kupio grof Auersperg, koji je za gradnju svojega novog grada u Kočevju iskoristio i materijal s Fridrihštajna. Poznata njemačka pripovjedačka braća Grimm još su 1795. godine izvijestila da u očuvanom dijelu grada živi lovac sa svojim slugama, pa je grad vjerojatno trajno napušten tek početkom 19. stoljeća.
Danas su od grada ostali tek porušeni zidovi i ostaci temelja. Lokalitet su 1993. godine počeli čistiti i stručno restaurirati. Trenutačno je zidovlje obnovljeno i time zaštićeno od daljnjeg propadanja. Obnovljen je dio bedema, a ruševine su poznato izletište. Posebnost koja je sačuvana iz tog vremena jest živa stijena na kojoj je ostao trag Veronike Deseniške. Legenda kaže da se stijena na kojoj je tada sjedila, kada ju je Friderik II. na dan vjenčanja poljubio, pod utjecajem njihove silne ljubavi rastopila.