The first mention of a house on the site dates from 1272. By the fifteenth century the manor of Woking was held in turn by various crown nominees until, in 1466, the royal grant passed it to Margaret Beaufort and Henry Stafford. Stafford was her third husband of four. He was killed in 1471 at the Battle of Barnet, fighting for Edward IV. Margaret remarried but kept the manor, and after her son took the throne as Henry VII in 1485, the first parliament of his reign granted her the right to hold property independently from her husband, as if she were unmarried - one of the few exceptions to coverture allowed in fifteenth-century law. She founded Christ's College and St John's College at Cambridge and was given, near the end of her son's reign, a special commission to administer justice in the north of England. Her portrait still hangs at St John's, an unsmiling Tudor matriarch in a black gable hood.

In 1503 Henry VII converted the manor house into a palace. Henry VIII visited often and approved a programme of regular alterations and upkeep: new windows, retiled fireplaces, replastered walls, new bridge planks, replacement glass. He commissioned a wharf on the River Wey to bring goods directly upriver from the Thames, and two new bowling alleys for play. Elizabeth I remodelled it again later in the century. The palace was moated on three sides, with the river enclosing the fourth, and it divided into four quarters. The northeast quadrant held service buildings. The southeast contained the medieval barrel vault and the King's Hall, the latter built by Henry VII in 1508. The King's Garden lay to the southwest. The northwest was orchard - now known simply as the Copse - with two long fishponds and a smaller round one. A 1400-1550 gold pin set with an amethyst fleur-de-lys, found on the site and now recorded under the Portable Antiquities Scheme, hints at the kind of life that went on inside the walls.

James VI and I came to Woking in March 1606. He was in the habit of visiting in the spring. While he was there, a false rumour reached London that he had been assassinated by Catholic conspirators armed with poisoned knives or pistol shot - the kind of plot, fresh after the Gunpowder Plot of November 1605, that the city was primed to believe. Whitehall Palace and the Tower of London were locked down. The king, unharmed and probably amused, hurried back to London, and the bells were rung at St Margaret's, Westminster, in thanks for his return. He kept coming back to Woking. In September 1624, when he was at Oatlands Palace, he wrote to the Duke of Buckingham that he would extend his stay because he was "so earnest I am to kill more of Zouch's great stags." The Zouch in question was the man James had made the next keeper of Woking.

Sir Edward Zouch, the Knight Marshal, was made steward of Woking by James in May 1609. He arranged with the surveyor of the royal works for cleaning the moat and building a private bridge that would shield the king's garden from the public road. James found his company useful in a particular way. At Oatlands the king would call for Zouch to play the fool, sing bawdy songs, and tell bawdy tales - a court jester ranked at the level of a knight. In 1620, with the crown chronically short of cash, Zouch was granted the estate outright for a rent of £100 a year and the symbolic duty of serving the first dish at the king's feast on St James's Day. He may well have begun stripping the buildings then to construct his own new house, Hoe Bridge Place, a mile away. He was also a proprietor of the Plymouth Colony and the North Virginia Company - one of the men whose money helped seed English settlement in America. In 1631 his own tenants drew up a long list of grievances and exploitations against him. He died not long after, leaving in his will a contribution to the maintenance of Old Woking Church and a strange final request: that he should be buried at night.

What remains today is described by archaeologists as an "excellent survival" among pre-sixteenth-century royal sites - excellent because so little above ground means almost everything still below ground is intact. The medieval barrel vault has been re-roofed by Woking Borough Council and fitted with a lockable door; protective repairs have been made to a stretch of Tudor wall. The King's Garden, once a formal kitchen garden, is now rough meadow. The moat is still wet on three sides, and the River Wey still encloses the fourth. The site is a Scheduled Ancient Monument. Walking it, you cross what was the courtyard where Margaret Beaufort entered to take possession in 1466, where Henry VII held his first court as the conqueror of Richard III's England, where Henry VIII bowled and Elizabeth I remodelled, where James I went hunting and Edward Zouch played the fool by night. The Friends of Woking Palace open it on selected days; an amethyst pin lies in the Portable Antiquities database, and the rest of the story remains underground.