Construction of the Castle, which follows the usual motte and bailey design favoured by the Normans, began in 1072 under the orders of William the Conqueror, six years after the Norman conquest of England, and soon after the Normans first came to the North. The construction took place under the supervision of Waltheof, Earl of Northumbria, until he rebelled against William and was executed in 1076. Stone for the new buildings was cut from the cliffs below the walls and moved up using winches.