Bishop Roger, son of the Earl of Leicester, raised the first castle here between 1189 and 1202. During the Wars of Scottish Independence the castle changed hands often enough that little of the original survives. Edward I of England took it after sacking Berwick in 1296. Bishop William Lamberton, Guardian of Scotland and an ally of Robert the Bruce, retook and repaired it after the Scottish victory at Bannockburn in 1314. The English recaptured it in the 1330s. Andrew Moray, Regent of Scotland, retook it again after a three-week siege. Then in 1336 or 1337 the Scots deliberately destroyed it, because castles taken twice tend to be lost three times. It lay ruinous for sixty years. Bishop Walter Trail rebuilt it around 1400 and died inside its walls the year after. His castle is the basis of what you see today: courtyard, kitchen tower, Sea Tower, and the truncated Fore Tower at the front.

Cut into the solid rock beneath the northwest tower is a pit. Twenty feet deep, shaped like a flask, narrow at the top and wider below, with no light, no ventilation, and no way out except through a trapdoor in the floor of the room above. This is the bottle dungeon, the most notorious prison in medieval Scotland. The Bishop's jurisdiction sent men down here for offences the burgh courts could not punish severely enough. David Stuart, Duke of Rothesay, was held here in 1402. Murdoch Stewart, 2nd Duke of Albany, in 1425. John Knox later wrote of it: Many of God's children were imprisoned here, meaning Protestant preachers and ordinary believers caught up in the persecutions of the 1530s and 1540s. Three women from Edinburgh and Dunfermline, convicted of witchcraft, were held in the castle and burned on 10 October 1542. The bottle dungeon is the kind of place that turns historical abstraction into the smell of damp rock and the imagination of what it must have been like to wait at the bottom of it.

Cardinal David Beaton took up residence in 1538. Much of what we know about life inside the castle comes from his household account books, which read like a chronicle of how a 16th-century prince of the church actually lived. The Widow Fallousdale brewed his beer. A drummer named William Blair was on retainer. Onion and lettuce grew in the castle garden. Coal came up by boat from West Wemyss. In 1541 a whale beached at Boarhills, just down the coast, was hauled to the castle and salted into barrels, a small economic event for the cathedral kitchens. A French military engineer, Christopher Grymmerschere, kept the artillery in order. Master Wolf cast new cannon. John Fynnyk was the gunner. Beaton had prepared for a siege he knew was coming: gabions, new guns, reinforced walls. The siege came. It did not save him.

On the first of March 1546, Beaton had the Protestant preacher George Wishart burned at the stake in front of the castle walls. On 29 May, Wishart's friends and a group of allied Fife lairds murdered the Cardinal in his chamber and hung his body from the front window. The siege that followed lasted eighteen months. The defenders dug a counter-mine through solid rock to meet the attackers' tunnel; both tunnels were rediscovered in 1879 and you can walk through them today, the most accessible siege mines of their period in Britain. John Knox entered the castle as the garrison's preacher during a 1547 truce. When a French fleet arrived under Leone Strozzi in July, the castle was rendered indefensible in six hours of bombardment from French guns mounted, with bitter irony, on the towers of St Andrews Cathedral itself. The Castilians were taken to France. Knox spent nineteen months chained to a galley oar. Archbishop John Hamilton rebuilt the castle after the siege. The Reformation eventually abolished the office of bishop in Scotland, and after 1689 the castle had no function. By 1656 the burgh council was already using its stones to repair the harbour pier. What remains is what survived being quarried: a square tower, a kitchen tower, the bottle dungeon, and the mine tunnels under the rock.