The Melrose Chronicle records that in 1162 a new church was founded at St Andrews by Bishop Arnold (1160-62), who had previously been abbot of Kelso. As the cathedral church of Scotland’s most important bishop, and as the home of its leading community of Augustinian Canons, St Andrews was of the highest significance for the Scottish Church. The new building was therefore conceived on a scale intended to leave neither the archbishops of York, who attempted to claim authority over the Scottish Church, nor his fellow Scottish bishops in any doubt as to its bishop’s standing and willingness to assert his seniority. The nave was nearing completion in the 1270s, when Scotichronicon says the west front was blown down in a storm, perhaps the same storm that damaged Arbroath Abbey in 1272. The western bays were then rebuilt by Bishop William Wishart (1271–79), and the whole cathedral was eventually dedicated on 5 July 1318.
A further extended period of rebuilding was necessitated by a major fire in 1378. The inclusion of the cathedral as ‘santandroys’ in the list of his works inscribed at Melrose Abbey by the Paris-born mason John Morow suggests that Morow’s contribution was part of the work that had to be initiated after that fire. Scotichronicon recorded that Prior Stephen Pay (1363–86) repaired the roof and stonework and rebuilt two piers on the south side of the nave, and that the work on the nave was continued by his successor, Prior Robert de Montrose (1386–94), who completed the work up to the rafters and covered the roof.
Scotichronicon records that on 13 January 1409/10 a storm blew down the south transept gable, damaging the dormitory, parlour and chapter house, fatally wounding the Sub-Prior, Thomas de Cupar, who was in the chapter house at the time.
The cathedral was 'cleansed' (despoiled) by the reformers in 1559, and soon after the Reformation Parliament of 1560 orders were given for it to be unroofed, after which the bishop used the nearby parish church of Holy Trinty as his cathedral. The abandoned cathedral's building materials were quickly put to other uses, and by 1693 the depiction of it in Slezer's Theatrum Scotiae shows that it was in much the same condition as now. Between 1837 and 1842 there was discussion as to how far the crown was responsible for the upkeep of the remaining fabric, with full responsibility eventually being accepted.