The building of Colchester Castle was probably begun in the 1070s or 80s. The Colchester Chronicle of the fourteenth century asserts the building work began in 1076 which would fit with reaction to the rebellion of Robert of Norfolk in 1075. The Castle is not mentioned in Domesday (1086) but that does not prove that it did not exist, in some form, by then.
Henry I granted the Castle to Eudo in 1101, who served as Steward (dapifer) of Normandy, for William I, II and Henry I. Following Eudo’s death in 1120 the Castle reverted to the crown. Thereafter it was generally held by a constable or keeper, appointed by the crown; very often the appointee was an absent noble who appointed deputies to carry out his duties.
In 1132 Henry I visited Colchester and the Castle at which time Hamo or Hamon de St Clare, a former under-tenant of Eudo, was the constable; he was succeeded by his son Hubert who died in 1155. It seems that at times there was no appointed constable or keeper and the Crown kept the Castle under direct control with the sheriff as the main judicial officer of the county holding the Castle. This seems to have been the case from 1155 to 1190 except for 1173-4 during the rebellion of Henry II’s sons when Ralph Brito was constable and the Castle was reinforced, supplied and garrisoned and wages paid to knights and serjeants.
About £24 had been spent on repairs in 1161; more work was carried out on the Castle and the king's houses in it in 1167 and 1170. In 1172-3, prior to the rebellion a bailey was constructed at a cost of £50. The bailey certainly had a stone wall by 1182-3 as it was repaired to a cost of £30 including construction of a lime kiln. In 1192 and 1195 60 marks was spent on repairs to the Castle and houses in it.
In 1196 William de Lanvalei became constable and in 1200 he purchased from King John, who had become king in 1199, the right to continue in his position at Colchester. King John came to Colchester, presumably staying at the Castle, in 1203, 1204 and 1205 and again in 1209 and 1212.
He was at Colchester for two days in early November 1214 and replaced de Lanvalei, who supported the barons, firstly it appears with the sheriff Matthew Mantell and then almost immediately with Stephen Harengoot possibly a Flemish supporter of the king or perhaps a mercenary. The Castle was repaired at a cost of 45 marks and garrisoned and the men of Colchester were given timber to enclose the Castle.
However, after the signing of the Magna Carta in July 1215 Harengoot had to hand it back to de Lanvalei. By October de Lanvalei was either dead or in rebellion and in late 1215 or early 1216 French troops came to strengthen the garrison for the barons. The Castle was besieged by Savory de Meuleon for the King in January 1216; it held out but surrendered to John in March. Harengoot became constable again and sheriff until 1217 when the Castle was surrendered, in return for a truce. It was restored to the crown by the treaty of Lambeth in 1218, provisioned, and put into the care of the Bishop of London.
The castle was first recorded as being used as a prison in 1226.