The castle keep was probably built by Milo Fitzwalter, Earl of Hereford, in the 12th century. In 1158 the Castle passed to the de Bohun family, when Milo's daughter Margaret married Humphrey de Bohun III. He added the curtain walls, the corner towers and the de Bohun gate.

The castle remained in the de Bohun hands until 1376 when it passed to Thomas Woodstock, youngest son of King Edward III. When he married Alianore de Bohun, he adds the gatehouse and Woodstock Tower.

Thomas was murdered on the orders of Richard II in 1397 and the castle subsequently passed to the Earl of Stafford by virtue of his marriage to Thomas's daughter, Anne. The Staffords held the castle until 1521 when the family fell foul of Henry VIII.

The castle then came into royal hands through the Duchy of Lancaster, until it was sold to the Lewis family of St Pierre in 1857. By this time the castle has been decaying for several centuries. In 1885 the ruins were sold to J R Cobb, a wealthy antiquarian, who set about restoring them. In 1963 the Cobbs sold the castle to Chepstow Rural Distict Council. It has been in local Authority hands ever since.