Okraj pohraničního hvozdu, jímž vedla důležitá zemská cesta přes Železnou Rudu do Bavor, střežila soustava hradů, k nimž patřila i Klenová. Stavebníky byli páni z Klenové, významný český rod.

Z raně gotické etapy výstavby zůstaly jen nepatrné zbytky. I přes složitý stavební vývoj se dochoval půdorys a stopy středověkého obranného systému. Val a příkop chránil původní hrad v místech, kde nebyla přirozená ochrana. Jednoduché opevnění jednou hradební zdí nemohlo stačit rozvoji palebných zbraní. Politik a zkušený válečník, proslulý kolísáním své politické orientace mezi podobojí a podjednou, Přibík z Klenové, uplatnil své vojenské zkušenosti při rozsáhlé přestavbě hradu. Promítl do ní vlastní znalost moderního způsobu opevnění. Za této pozdně gotické přestavby trvající až do sklonku 15. století (i po Přibíkově smrti) byl obranný systém posílen vnější hradební zdí zesílenou hranolovitými půlválcovými baštami, které umožňovaly boční palbu. Nádvoří a zdi obklopily nové budovy, k jedné ze zdí přiléhala kaple, na nejlépe chráněném místě vyrostl trojkřídlý palác.

Renesančními prvky s nástěnnými malbami obohatili přestavěné budovy noví majitelé, Harantové z Polžic a Bezdružic. (Na hradě se snad dokonce narodil Kryštof Harant, humanista, skladatel a cestovatel, popravený roku 1621 na Staroměstském náměstí v Praze.)