On ne sait pas précisément à quelle date la construction du château de Colchester a débuté, mais c'était probablement autour de 1070 ou 1080, sur les ordres de Guillaume le Conquérant. Le Château fut bâti sur un vaste socle de pierre qui avait dans le passé fait partie du temple romain dédié à l'empereur Claude. Ainsi, Guillaume le Conquérant associait son autorité à celle des empereurs romains qui l'avait précédé.
Le donjon, qui mesure 46 m x 33,5 m, est le plus grand donjon bâti par les Normands encore en existence. En Angleterre, son plan au sol est le seul qui est similaire à celui de la Tour blanche de la Tour de Londres, ce qui suggère que Gundulf, évêque Rochester est probablement l'architecte des deux bâtiments.
La pénurie de matériaux de construction de bonne qualité ayant persuadé les Normands d'utiliser les ruines de la Colchester romaine, cette dernière leur fournit la majorité des pierres et des briques. Le Château fut bâti en deux étapes. Le donjon de la première phase était de plain-pied, comme le montrent les remparts que l'on peut encore clairement distinguer sur certaines parties des murs extérieurs. La deuxième phase de construction commença vers 1106 et fut confiée à Eudes, qui avait été au service des trois premiers rois normands en tant que sénéchal de Normandie. Les murs furent alors surélevés, mais leur hauteur exacte demeure encore sujet de débat. Traditionnellement, on a pensé que le Château avait trois niveaux. Néanmoins, des découvertes récentes ont conduit à reconsidérer cette théorie et suggèrent que la hauteur du Château a toujours été plus ou moins ce qu'elle est aujourd'hui.
De nombreuses et significatives caractéristiques normandes peuvent encore être admirées de nos jours dans le Château. Dans le passé protégé par un avant-corps, le portail, orné d'un arc délicat, fut construit en partie en pierre de Caen transportée de Normandie. Le Grand Escalier, situé dans la tour sud-ouest, est le plus grand escalier hélicoïdal de Grande-Bretagne. Les cheminées du premier étage sont des exemples précoces de cheminées possédant une mitre en forme de Y d'où la fumée peut s'évacuer par des trous. Les appartements royaux étaient situés dans la galerie est, au premier étage, un fait établi par la présence d'une chapelle ou crypte adjacente et de toilettes!
Autour du donjon se trouve un large fossé, dont les parties nord et est sont encore pratiquement intactes. Dans cet espace, appelé “basse-cour”, seules les fondations d'une chapelle peuvent être encore contemplées, bien que cet endroit ait probablement abrité de nombreux autres bâtiments (écuries, entrepôts et ateliers). Au nord du donjon, une basse-cour inférieure s'étendait jusqu'aux murs de la ville.
Le Château demeura une forteresse royale durant toute la période normande et fut le théâtre de combats une seule fois, en 1216, lorsque le roi Jean (Jean sans Terre) dut le reprendre aux troupes françaises qui l'occupaient car alliées aux barons anglais en révolte.