Hrad byl založen mezi roky 1290 - 1310, jako rodové sídlo pánů z Velhartic. Stavbu započal Albert z Budětic, pokračoval Bušek starší a jeho syn Bušek mladší z Velhartic, oba oblíbení a věrní komorníci krále a císaře Karla IV.

Dle doposud nám dostupných poznatků byl hrad v nejrannější podobě tvořen vysokou obvodovou hradbou s cimbuřím, situován na nejjižnější partii skalního ostrohu (dnešní horní nádvoří). Hradba zprvu kryla patrně spíše dřevěné či hrázděné stavby. Během dalšího vývoje byl na této hradbě zbudován nejprve jižní, následně severní kamenný hradní palác. Jádro hradu poté tedy tvořily dva paláce vzájemně propojené hradbami - tehdy módní tzv. dvoupalácová dispozice, zde přizpůsobená terénní situaci.

Severní palác, reprezentativní Rajský dům, stojí na nejvyšším místě hradní skály. Je to stavba značné výšky a zajímavého půdorysu - ve tvaru písmene D. Kamenné je u tohoto paláce pouze obvodové zdivo, vnitřní konstrukce byly výhradně dřevěné. Zajímavé jsou okenní otvory paláce, které naznačují jeho stavební vývoj - od nejstaršího sdruženého okénka , přes obdélné otvory s jednoduchým ostěním, až k oknům se středním kamenným prutem. Z jihozápadního rohu paláce vybíhá hradba (nyní již pouze zbytek) uzavírající horní nádvoří od jihozápadu. Součástí této hradby je výrazný gotický portál u vchodu na horní nádvoří. Hradba uzavírající nádvoří ze strany východní se nám zachovala ne příliš narušena, jelikož tvoří zadní stěnu pozdně renesančního Huertova křídla. Tato hradba přechází v druhý gotický palác situovaný na nejjižnějším cípu hradního ostrohu. V hradbě jsou dvě řady střílnovitých okének a gotický portálek výpadové branky, umožňující přístup na parkán za Rajským domem. Jižní gotický palác se stal při přestavbách v 17. století součástí Huertova křídla.

Aby bylo lépe kryto poměrně snadno přístupné severozápadní čelo hradu, byla vybudována předsunutá velká hranolová obytně-obranná věž, která ho kryla svou hmotou. Její zdivo je masivní, více jak 2,5 m silné. Ve značné výšce je její severovýchodní zeď proražena několika úzkými větracími otvory a nad nimi okny s jednoduchým pravoúhlým ostěním. Uvnitř, asi ve výši druhého poschodí, je hrotitý portálek ke schodišti, které vedlo v síle zdi do hořejších pater. Jediný možný přístup do věže byl po padacím můstku z velkého kamenného mostu - tedy až v úrovni druhého podlaží. Průraz v přízemí, nyní upravený do podoby vchodového profilu, je důsledkem zásahů v předminulém století.

Originální spojovací článek mezi jádrem hradu a předsunutou obytně-obrannou věží je již zmíněný velký kamenný most - stavba, která v hradních areálech střední Evropy nemá obdoby. Je dlouhý 32m, široký 3m a vysoký téměř 10m, se čtyřmi lomenými oblouky na masívních válcovitých pilířích. Tato stavba umožňovala poměrně zajímavý a progresivní způsob obrany hradu v případě jeho dobývání. Kdyby se nepříteli podařilo zmocnit paláce, mohli obránci hradu ustoupit z jeho druhého patra na most, který mohl být dočasně hájen, a tím zpomalit postup nepřítele k poslednímu opěrnému bodu hradní obrany - velké věži. V ní mohl zbytek posádky klást poslední odpor. Pochopitelně byl možný i postup opačný, od velké věže k Rajskému domu, přičemž padací můstky na obou stranách mostu dovolovaly přístup oboustranně znemožnit.

Obranyschopnost hradu byla ještě zvýšena v 15. století hradbou obepínající celou severovýchodní a jihozápadní partie hradu, přecházející v hluboký ve skále tesaný suchý hradní příkop. Součástí této hradby byla vrátnice s širokým gotickým portálem, kterým se do hradu vstupuje, a tehdy moderní flankovací a hrotité bašty, umožňující efektivnější obranu hradeb. Přechod přes hradní příkop umožňoval dřevěný padací most. Na spodním nádvoří, které bylo novou hradbou obehnáno vyrostly rozličné hospodářské stavby. Nejvýraznější z nich je stavba dvouštítového hradního pivovaru. Stavba nepravidelného půdorysu, která pohledově nádherně vyvažuje úzkou a vysokou stavbu jižního gotického paláce.

V držení rodu pánů z Velhartic zůstal hrad do roku 1390, kdy sňatkem přešel v majetek Jana z Hradce, jehož syn Menhart, nejvyšší purkrabí Království českého, odpůrce Jiřího z Poděbrad, často sídlil na Velharticích. Chtěje znemožnit korunovaci Jiřího z Poděbrad na krále, ukryl Menhart korunovační klenoty Království českého, k nimž měl vzhledem ke své funkci přístup, tajně na velhartickém hradě. Tím byly zdi tohoto hradu poctěny důvěrou nevšední. Jedním z dalších významných držitelů hradu byl v 15 stol. Zdeněk Lev z Rožmitálu který získal pro velhartické panství několik dalších privilegií např. možnost těžit drahé kovy.

Doba třicetileté války zastihla velhartický hrad v nepříliš utěšeném stavu a tak se císařský plukovník Martin de Hoeff Huerta, který jej jako konfiskovaný majetek získal, rozhodl pro jeho rozsáhlou přestavbu. Za jeho držení byl vystavěn ve východní části horního nádvoří nový pozdně renesanční palác. Jméno Martina de Hoeff Huerty provází z období jeho vlády na velhartickém panství mnoho hrůzostrašných pověstí - se svými třiceti jezdci tvrdě rekatolizoval zdejší kraj. Že jeho působení na Velharticích však nebylo pro poddané jenom utrpením dokazuje to, že pro velhartické např. zrušil robotu.