The building of the castle was left to Baldwin FitzGilbert who was appointed castellan, amongst other honours. A deep ditch and internal rampart were constructed between the north-western and north-eastern city walls, forming a roughly square enclosure with sides of about . The "Domesday Book" of 1086 reported that 48 houses had been destroyed in Exeter since the King came to England—this has been interpreted by historians to mean that this many houses were on the site cleared for the castle. A large stone gatehouse, which still survives, was built into the bank at the south side of the enclosure. It has clear elements of Anglo-Saxon architecture, such as long-and-short quoins and double triangular-headed windows, suggesting that it was built very early by English masons on the Normans' orders. At this early stage the rampart was probably surmounted by a stockade, though two corner turrets were soon built where the bank met the city walls, the western one of which (mistakenly known as "Athelstan's Tower") is still present.