The castle was founded between 1290 and 1310 as the family residence of the squires of Velhartice. Commenced under Bohumil of Budětice, the construction works were continued by Bušek the Elder and his son Bušek the Younger of Velhartice who were favourite and loyal chamberlains of King and Emperor Charles IV.

According to hitherto available data, the castle in its earliest origins was situated atop the southernmost ledge of a rocky crag (currently the upper courtyard), with a high castellated peripheral rampart probably hiding wooden or half-timbered structures. In the course of the further development, first the castle's south stone palace was erected on the rampart, followed by the north palace. Consequently, the castle's central portion was composed of two palaces interconnected by walls. Hence, the then fashionable double-palace disposition was accommodated to the surrounding terrain.

Remarkable for its considerable height and interesting ground plan, the D-shaped north palace - the representative Paradise House, occupies the highest position of the castle rock. As far as this palace concerns, stones were only used to erect its peripheral masonry rampart; its inside structural system was entirely made of timber. Noteworthy are the palace's window openings suggesting its architectural development - from the most ancient coupled window to oblong openings with simple jambs to windows with central mullions. Jutting out from the palace's southwest corner, the remains of the wall close the upper courtyard from the southwest. The wall features a remarkable Gothic portal adorning the entrance of the upper courtyard. The rampart closing the courtyard from the east has been preserved in a fairly intact condition, since it forms the rear wall of the late Renaissance Huerto's Wing. That rampart merges into the other Gothic palace situated in the southernmost area of the castle crag. The rampart is provided with two lines of loopholes and a Gothic portal of the sallyport enabling the access to the rear ward behind the Paradise House. During the remodelling in the 17th century, the south Gothic palace was incorporated into the Huerto's Wing.

To bolster the defence of the relatively easily accessible northwest castle front, the advanced bulky prismatic residential tower - donjon - was erected there to protect the castle by its mass. Its huge masonry walls are more than 2.5 m thick. In a considerable height of the northeast wall there are several narrow air holes below windows with simple rectangular jambs. Inside, approximately on the level of the second storey there is a pointed portal of the staircase leading in the thickness of the wall up to upper storeys. The only possible way how to enter the tower was to cross the fall-bridge situated on the big stone bridge, i.e. on the level of the second storey. Broken through in the aftermath of construction works in the 19th century, the ground-floor opening has been reshaped as the entrance profile.

Unrivalled in castle sites of Central Europe, the above mentioned big stone bridge served as the link between the castle's central portion and the advanced donjon. It is 32 m long, 3 m wide and almost 10 m high, with four pointed arches supported by massive cylindrical pillars. This structure enabled relatively sophisticated and progressive defence of the castle against conquerors. If the enemy had succeeded in capturing the palace, the defenders would have been able to retreat from the palace's second floor onto the bridge that could have been temporarily protected, thereby slowing down the enemy's advance to the ultimate stronghold of the castle defence, namely, to the large tower (donjon). Inside the tower the remaining defenders were able to put up final resistance. Of course, the reverse movement was possible as well, i.e. from the large tower to the Paradise House, with fall-bridges on both sides of the bridge preventing the conquerors from gaining access from both directions.

In the 15th century, the castle's defence system was reinforced by a rampart encircling the whole northeast and southwest sections of the castle and merging into a deep dry moat hewn deep into the rock. The rampart included a gatehouse with a wide Gothic portal used to enter the castle site, with the then modern pointed flanker facilitating more efficient defence of the walls, and a wooden fall-bridge serving to cross the moat. Enclosed by the new rampart, various farmstead structures were built on the lower courtyard, the most noteworthy of them being the double-gabled castle brewery. At the sight of the castle, this irregular structure beautifully counterbalances the slender and high edifice of the south Gothic palace.

The squires of Velhartice kept the castle till 1390 when it was acquired by marriage by Jan of Hradec whose son Menhart, the High Burgrave of the Bohemian kingdom and adversary to Regent George of Poděbrady was then frequently residing at Velhartice. In order to prevent George of Poděbrady from being crowned King, Menhart secretly concealed crown jewels of the Bohemian kingdom (he had access to them on account of his title) in Velhartice Castle, thereby honouring the castle walls with unusual trust. In the 15th century, one of the castle's significant owners was Zdeněk Lev of Rožmitál who gained several other privileges for the Velhartice estate, among others the right to extract there precious metals. The Thirty Years' War found Velhartice Castle in a rather dismal condition. Consequently, after acquiring the confiscated Velhartice estate, Martin de Hoeff Huerto, General of the Emperor's army, decided to carry out comprehensive remodelling of the castle. Hence, under Huerto a new late Renaissance palace was erected in the east section of the upper courtyard. Martin de Hoeff Huerto's name has been associated with many scary legends describing his rule in the Velhartice domain, featuring him and his thirty horsemen ruthlessly endeavouring to re-catholicize this region. On the other hand, taking into consideration the fact that he abolished the corvée (compulsory unpaid labour) for the local inhabitants, his rule at Velhartice did not bring only suffering to his serfs.