Today the River Fleet has been reduced to a trickle in a culvert under New Bridge Street that emerges under Blackfriars Bridge, but before the development of London it was the largest river in the area after the Thames. It formed the western boundary of the Roman city of London and the strategic importance of the junction of the Fleet and the Thames means that the area was probably fortified from early times. Richard of Cirencester suggests that Canute spent Christmas at such a fort in 1017, where he had Eadric Streona executed. Some accounts claim this was triggered by an argument over a game of chess; Historian William Page suggests that Eadric held the fort as Ealdorman of Mercia and after his death it may have been granted to Osgod Clapa, who was a "staller", a standard-bearer and representative of the king (see Privileges section).
This fort was apparently rebuilt after the Norman invasion by Ralph Baynard, a follower of William the Conqueror and sheriff of Essex. It was on the riverfront inside the Roman walls; a second Norman fort, Montfichet's Tower was 70 metres (230 ft) to the north. The site of Baynard's Castle was adjacent to the church of St. Andrew-by-the-Wardrobe, on the southern side of 160 Queen Victoria Street (the former Times office and now The Bank of New York Mellon Centre); archaeologists have found fortifications stretching at least 50 metres (160 ft) south, onto the site of the proposed development at 2 Puddle Dock. This may be the Bainiardus mentioned in the Domesday Survey (1087) who gave his name to springs near Paddington called Baynard's Watering, later shortened to Bayswater.
The castle was inherited by Ralph's son Geoffrey and his grandson William Baynard, but the latter forfeited his lands early in the reign of Henry I (1100–1135) for supporting Henry's brother Robert Curthose in his claim to the throne. After a few years in the hands of the king, the castle passed to Eustace, Count of Boulogne by 1106. John Stow gives 1111 as the date of forfeiture. Later in Henry's reign, the lordship of Dunmow and honour or soke of Baynard's Castle were granted to the king's steward, Robert Fitz Richard (1064–1136). The soke was coterminous with the parish of St. Andrew-by-the-Wardrobe, which was adjacent to the Norman castle; the soke roughly corresponds to the eponymous ward of the City of London. Both Dunmow and Baynard's Castle were eventually inherited by his grandson, Robert Fitzwalter (d. 1234).