The church occupies the site of the ancient chancel and transepts of a large medieval Benedictine abbey, which was confiscated and sacked in 1560 during the Scottish Reformation and permitted to fall into disrepair.

The Benedictine Abbey of the Holy Trinity and St Margaret, was founded in 1128 by King David I of Scotland, but the monastic establishment was based on an earlier priory dating back to the reign of his father King Máel Coluim mac Donnchada, i. e. "Malcolm III" or "Malcolm Canmore" (regnat 1058–93), and his queen, St Margaret.

At the peak of its power it controlled four burghs, three courts of regality, and a large portfolio of lands from Moray in the north south to Berwickshire.

By September 1563 the choir and feretory chapel were roofless, and it was said that the nave was also in a sorry state, with the walls so extensively damaged that it was a danger to enter.

The tomb of Saint Margaret and Malcolm Canmore, within the ruined walls of the Lady chapel, was restored and enclosed by command of Queen Victoria.

[6] Another rich Romanesque doorway was exposed in the south wall in 1903, when masons were cutting a site for the memorial to the soldiers who had fallen in the Second Boer War.