St Machar is said to have been a companion of St Columba on his journey to Iona. A fourteenth-century legend tells how God (or St Columba) told Machar to establish a church where a river bends into the shape of a bishop's crosier before flowing into the sea. The River Don bends in this way just below where the Cathedral now stands.
According to legend, St Machar founded a site of worship in Old Aberdeen in about 580. Machar's church was superseded by a Norman cathedral in 1131, shortly after David I transferred the See from Mortlach to Aberdeen. Almost nothing of that original cathedral survives; a lozenge-decorated base for a capital supporting one of the architraves can be seen in the Charter Room in the present church.
After the execution of William Wallace in 1305, his body was cut up and sent to different corners of the country to warn other dissenters. His left quarter ended up in Aberdeen and is buried in the walls of the cathedral.
At the end of the thirteenth century Bishop Henry Cheyne decided to extend the church, but the work was interrupted by the Scottish Wars of Independence. Cheyne's progress included piers for an extended choir at the transept crossing. These pillars, with decorated capitals of red sandstone, are still visible at the east end of the present church. Bishop Alexander Kininmund II demolished the Norman cathedral in the late 14th century, and began the nave, including the granite columns and the towers at the western end. Bishop Henry Lichtoun completed the nave, the west front and the northern transept, and made a start on the central tower. Bishop Ingram Lindsay completed the roof and the paving stones in the later part of the fifteenth century. Further work was done over the next fifty years by Thomas Spens, William Elphinstone and Gavin Dunbar; Dunbar is responsible for the heraldic ceiling and the two western spires. The central tower and spire collapsed in 1688, in a storm, and this destroyed the choir and transepts. The west arch of the crossing was then filled in, and worship carried on in the nave only; the current church consists only of the nave and aisles of the earlier building.