Die Burg wurde in den Jahren 1290 bis 1310 als Familiensitz der Herren von Velhartice gegründet. Die Bauarbeiten begannen während der Herrschaft von Bohumil von Budětice, der Bau wurde von Bušek sen. und seinem Sohn Bušek jun. von Velhartice fortgesetzt, die beliebte und loyale Kammerherren des Königs und Kaisers Karl IV. waren.
 
Nach den bisherigen Erkenntnissen befand sich die Burg in ihren frühesten Anfängen auf dem südlichsten Felsvorsprung (heute Oberhof), mit einem hohen, zinnenförmigen Randwall, in dem sich wahrscheinlich Holz- oder Fachwerkbauten verbargen. Im Zuge der weiteren Entwicklung wurde auf dem Wall zunächst der südliche Steinpalast der Burg errichtet, dann der Nordpalast. Folglich bestand der zentrale Teil der Burg aus zwei Palästen, die durch Mauern miteinander verbunden waren. Daher wurde die damals modische Doppelpalast-Disposition dem umgebenden Gelände angepasst.

Bemerkenswert durch seine beachtliche Höhe und seinen interessanten Grundriss, nimmt der D-förmige Nordpalast - das repräsentative Paradieshaus, die höchste Position des Burgfelsens ein. Was diesen Palast betrifft, so wurden Steine nur für die Errichtung des peripheren gemauerten Walls verwendet; Sein inneres Konstruktionssystem wurde vollständig aus Holz gefertigt. Bemerkenswert sind die Fensteröffnungen des Palastes, die auf seine architektonische Entwicklung hindeuten - vom ältesten gekoppelten Fenster über längliche Öffnungen mit einfachen Pfosten bis hin zu Fenstern mit zentralen Pfosten. Die Reste der Mauer ragen aus der Südwestecke des Palastes hervor und schließen den oberen Hof von Südwesten her ab. An der Mauer befindet sich ein bemerkenswertes gotisches Portal, das den Eingang zum oberen Hof schmückt. Die Stadtmauer, die den Hof von Osten her abschließt, ist in einem ziemlich intakten Zustand erhalten geblieben, da sie die Rückwand des Huerto-Flügels der Spätrenaissance bildet. Dieser Wall geht in den anderen gotischen Palast über, der sich im südlichsten Teil des Burgfelsens befindet. Der Wall ist mit zwei Reihen von Schießscharten und einem gotischen Portal versehen, das den Zugang zum hinteren Trakt hinter dem Paradieshaus ermöglicht. Während des Umbaus im 17. Jahrhundert wurde der südgotische Palast in den Huerto-Flügel integriert.

Um die Verteidigung der relativ leicht zugänglichen nordwestlichen Burgfront zu verstärken, wurde dort der vorgeschobene, wuchtige prismatische Wohnturm - Donjon - errichtet, um die Burg durch seine Masse zu schützen. Das riesige Mauerwerk ist mehr als 2,5 m dick. In beträchtlicher Höhe der Nordostwand befinden sich unter den Fenstern mehrere schmale Luftlöcher mit einfachen rechteckigen Pfosten. Im Inneren, etwa auf Höhe des zweiten Stockwerks, befindet sich ein spitz zulaufendes Portal der Treppe, das in der Wandstärke zu den oberen Stockwerken hinaufführt. Die einzige Möglichkeit, in den Turm zu gelangen, bestand darin, die Fallbrücke zu überqueren, die sich auf der großen Steinbrücke befand, d.h. auf der Höhe des zweiten Stockwerks. Nach Bauarbeiten im 19. Jahrhundert durchbrochen, wurde die Öffnung des Erdgeschosses zum Eingangsprofil umgestaltet.

Die oben erwähnte große Steinbrücke, die unter den Burganlagen Mitteleuropas ihresgleichen sucht, diente als Bindeglied zwischen dem zentralen Teil der Burg und dem vorgeschobenen Donjon. Er ist 32 m lang, 3 m breit und fast 10 m hoch, mit vier Spitzbögen, die von massiven zylindrischen Säulen getragen werden. Diese Struktur ermöglichte eine relativ ausgeklügelte und fortschrittliche Verteidigung der Burg gegen Eroberer. Wäre es dem Feind gelungen, den Palast einzunehmen, hätten sich die Verteidiger aus dem zweiten Stock des Palastes auf die Brücke zurückziehen können, die vorübergehend hätte geschützt werden können, wodurch der Vormarsch des Feindes zur letzten Festung der Burgverteidigung, nämlich zum großen Turm (Donjon), verlangsamt worden wäre. Im Inneren des Turms konnten die verbliebenen Verteidiger letzten Widerstand leisten. Natürlich war auch die umgekehrte Bewegung möglich, d.h. vom großen Turm zum Paradieshaus, mit Fallbrücken auf beiden Seiten der Brücke, die den Eroberern den Zugang aus beiden Richtungen verwehrten.

Im 15. Jahrhundert wurde das Verteidigungssystem der Burg durch einen Wall verstärkt, der den gesamten nordöstlichen und südwestlichen Teil der Burg umgab und in einen tiefen, trockenen, tief in den Fels gehauenen Graben überging. Die Stadtmauer umfasste ein Torhaus mit einem breiten gotischen Portal, das zum Betreten des Burggeländes diente, mit der damals modernen spitzen Flanke, die eine effizientere Verteidigung der Mauern ermöglichte, und einer hölzernen Fallbrücke, die zur Überquerung des Grabens diente. Von der neuen Stadtmauer umschlossen, wurden im unteren Hof verschiedene Gehöftbauten errichtet, von denen die Doppelgiebel-Schlossbrauerei am bemerkenswertesten ist. Beim Anblick der Burg bildet diese unregelmäßige Struktur ein schönes Gegengewicht zu dem schlanken und hohen Gebäude des südgotischen Palastes.

Die Burgherren von Velhartice besaßen die Burg bis zum Jahre 1390, als sie durch Heirat mit Jan von Hradec erworben wurde, dessen Sohn Menhart, der oberste Burggraf des Königreichs Böhmen und Gegner des Regenten Georg von Poděbrady, sich in dieser Zeit oft in Velhartice aufhielt. Um zu verhindern, dass Georg von Poděbrady zum König gekrönt wurde, versteckte Menhart heimlich Kronjuwelen des böhmischen Königreichs (zu denen er aufgrund seines Titels Zugang hatte) und beehrte so die Burgmauern mit ungewöhnlichem Vertrauen. Im 15. Jahrhundert war einer der bedeutenden Besitzer der Burg Zdeněk Lev von Rožmitál, der einige andere Privilegien für das Gut Velhartice erhielt, unter anderem das Recht, dort Edelmetalle abzubauen. Der Dreißigjährige Krieg fand die Burg Velhartice in einem ziemlich trostlosen Zustand vor. Martin de Hoeff Huerto, General der kaiserlichen Armee, beschloss daher, nach dem Erwerb des konfiszierten Anwesens Velhartice eine umfassende Renovierung des Schlosses durchzuführen. So wurde unter Huerto im östlichen Teil des oberen Hofes ein neuer Spätrenaissance-Palast errichtet. Der Name Martin de Hoeff Huerto ist mit vielen gruseligen Legenden verbunden, die seine Herrschaft in der Domäne Velhartice beschreiben und ihn und seine dreißig Reiter zeigen, die sich rücksichtslos um eine Wiederholholung dieser Region bemühen. Andererseits, wenn man bedenkt, dass er die Corvée (unbezahlte Zwangsarbeit) für die Einwohner abschaffte, brachte seine Herrschaft in Velhartice nicht nur Leid für seine Leibeigenen.