L'édification du château de Colchester commença probablement dans les années 1070 ou 1080. La Chronique de Colchester du XIVe siècle affirme que les travaux démarrèrent en 1076, ce qui correspondrait bien aux conséquences de la rébellion de Robert de Norfolk en 1075. Aucune référence au Château n'est présente en 1086 dans le Doomsday Book (“Livre du Jugement dernier”), ce qui ne signifie pas pour autant qu'il n'existait pas à l'époque sous une forme ou une autre.
En 1101, Henri 1er Beauclerc octroya le Château à Eudes, sénéchal (“Dapifer”) de Normandie pour Guillaume le Conquérant (Guillaume 1er), Guillaume II, dit Guillaume le Roux et Henri 1er Beauclerc. À la mort d'Eudes en 1120, le Château revint à la Couronne. Par la suite, il fut le plus souvent tenu par un connétable ou un gardien, nommé par la Couronne. Très souvent, le détenteur de la charge était un membre de la noblesse, lui-même absent et qui nommait des suppléants pour accomplir ses fonctions.
En 1132, Henri 1er Beauclerc visita Colchester et son Château, dont à l'époque Hamon de St-Clair, lui-même un ancien vassal d'Eudes, était le connétable. Son fils Hubert lui succéda à sa mort en 1155. Il semblerait qu'à certaines périodes il n'y ait eu aucun connétable ou gardien et que la Couronne contrôlait le Château directement avec le magistrat local. Cela est probablement le cas entre 1155 et 1190, sauf pour les années 1173 et 1174, durant la rébellion des fils d'Henri II. À ces dates-là Ralph Brito était le connétable et le Château fut consolidé, fourni, doté d'une garnison et un solde payé aux chevaliers et aux sergents d’armes.
En 1161, la somme de £24 fut dépensée en rénovations. En 1167 et 1170 des travaux supplémentaires furent effectués dans le Château et les maisons royales situées dans son enceinte. En 1172 et 1173, avant la rébellion, une basse-cour coûtant £50 fut bâtie. Vers 1182-1183, cette basse-cour était très certainement entourée d'un mur en pierre, car celui-ci fut réparé et un four à chaux construit pour la somme de £30. En 1192 et 1195, 60 marcs furent dépensés pour réparer le Château et les maisons qui en faisaient partie.
En 1196, Guillaume de Lanvallei devint connétable et en 1200, il racheta au roi Jean (Jean sans Terre), devenu roi en 1199, le droit de rester à son poste à Colchester. Le roi Jean vint à Colchester et séjourna probablement au Château en 1203, 1204, 1205 et à nouveau en 1209 et 1212.
Il resta deux jours à Colchester au début de novembre 1214, où il remplaça de Lanvallei, qui soutenait les barons. Il nomma à sa place d'abord Matthew Mantell, le magistrat local, puis, peu de temps après, Stephen Harengoot, qui était peut-être un partisan flamand du Roi ou un mercenaire. Des réparations furent effectuées au prix de 45 marcs. Une garnison fut postée et du bois donné aux hommes pour bâtir une palissade autour du Château.
Néanmoins, après la signature de la Magna Carta en juillet 1215, Harengoot dut restituer le Château à Lanvallei. En octobre de la même année, Lanvallei était mort ou en rébellion. En effet, à la fin de 1215 ou au début de 1216, des troupes françaises vinrent renforcer la garnison en soutien aux barons. Le Château fut assiégé au nom du roi par Savary de Mauléon en janvier 1216. Il résista pour finalement se rendre au roi Jean en mars. Harengoot redevint connétable et magistrat local jusqu'en 1217, lorsque le Château fut restitué en échange d'une trêve. En 1218, il fut restauré et équipé par la Couronne grâce au traité de Lambeth, pour être ensuite confié à l'évêque de Londres.
La première référence du Château en tant que prison date de 1226.