The first castle at Middleham was a motte and bailey design and the earthworks can still be seen 500 yards to the east of the present castle. It was raised to guard Coverdale and protect the road from Richmond to Skipton. The present castle began to be constructed around 1170 by Robert Fitz Randolph during the reign of Henry II when he built the keep and original bailey.

The keep is one of the largest in England having twelve foot thick walls and three floors. It was residential and contained a great chamber, kitchen, chapel, dovecot and cellars. At either end of the keep's vaulted basement there are two wells. The curtain walls are thirteenth century, forming an enclosure around 250 feet on each side. The towers on the four corners were added a century later. For extra defence a wide ditch was dug around these walls and access to the castle was by a gatehouse with a drawbridge in the north-east corner. In the fourteenth and fifteenth century the garrisons quarters, stables and stores were within these walls.

In the fifteenth century Middleham Castle was the northern seat of the Neville family and became a royal residence under Richard III. It is said that Richard's son Prince Edward was born in the south-west, or Prince's Tower.