Henry I of England built a hunting lodge here and in 1129 he built 7 miles (11 km) of walls to create the first enclosed park, where lions and leopards were kept. The lodge became a palace under Henry's grandson, Henry II, who spent time here with his mistress, Rosamund Clifford.
Important events that took place at the palace include:
- The marriage of William the Lion, king of Scots to Ermengarde de Beaumont in 1186
- The signing of the Treaty of Woodstock between Henry III of England and Llewelyn the Last (1247)
- The birth of Edmund, youngest son of King Edward I of England (1301)
- The birth of Edward, the Black Prince (1330)
- The marriage of Mary Plantagenet, daughter of Edward III of England, to John V, Duke of Brittany (1361)
- Imprisonment of the future Queen Elizabeth I of England (1554–58)