A Romanesque impost block with chip-carving and a wheel-headed cross missing the lower original arm are preserved inside the former cathedral church. Along with other medieval stone fragments, they have been kept inside since at least 1906. In 2000, the cross head was repaired and mounted onto a modern shaft. It is presently (2020) sited in the south aisle of the church. The impost block is kept in a room above the S porch. Restoration work on the church was carried out in 1832, 1867-8, 1926-8,1965-73 and 1976-91. No Romanesque work is known to suvive within the existing fabric of the church.

The earliest bishop of Aberdeen, Nechtan, was first based in Mortlach, but he moved to Aberdeen when the seat of the bishopric was established there by King David I, most likely in the 1130s. A small church seems likely to have been used initially as the cathedral church, but nothing is known about it. In 1157, Pope Adrian IV gave Bishop Edward permission to institute monks or canons into his cathedral. Boece (Hectoris Boetii), writing in the early 16th century, states that a new church began to be built by the end of King Malcolm IV’s reign in 1165, but it appears that it was during the reign of King William the Lion (1165-1214), under Bishop Matthew Kininmund/Kyninmund (1172-99), that the main part of the construction took place. Building work on the present church was started by Bishop Henry le Cheyne (1281/2 - 1328/9). This was interrupted by the wars with England, but King Robert I ordered that the new choir be completed at the bishop’s expense as soon as peace was restored. His successor, Bishop Alexander de Kininmund/Kyninmund I (1329-43/4) or Bishop William Deyn (1344-1350) must have completed the choir as Bishop Deyn was buried there at his death in 1350. Bishop Alexander de Kininmund/Kyninmund II (1355-80) started a 'new' church, thought to relate to the crossing and nave, and began construction of the west towers, but it was Bishop Henry de Lichton/Lichtoun (1422-40) who completed the nave and towers. Bishop William Elphinstone (1483-1514) completed the central tower and began to build a new choir, though this may never have been completed. Bishop Gavin Dunbar (1518-32), however, added spires to the W towers and had the nave ceiling decorated. Whatever was built of the choir appears to have become ruinious following the Reformation of 1560 and was screened off at the east side of the crossing.

The cathedral church is sited in the part of Aberdeen called Old Aberdeen. It is not certain where either the cross or the impost block were found. Cameron proposed a date between 1185 and 1215 for the cross head and suggested that it might have come from the cross that is known to have stood near the bishop's palace, east of the cathedral church. The most frequently sited comparison for the Aberdeen cross is that in the church of St Helen in Kelloe (Co. Durham), which is usually given a date of about 1200. Other similar Romanesque crosses, with flared arms and rounded outer edges exist at a few sites elsewhere, as at Durham Cathedral, there on a cross head which also has a central rosette (now stored in the cathedral lapidarium). It seems not unlikely that the cross at Aberdeen dates from the late-12th century.

The impost block is stylistically earlier than the cross. Decorated imposts are found commonly, but the use of chip-carving in Scotland, like that on the Aberdeen impost, is not normally found later than the mid-decades of the 12th century.

Sources for dating the move of the seat of Aberdeen from Morlach to Aberdeen are not in agreement. The dates offered by various writers in the past are usually given as about 1125, 1131/2 and 1136/7. Bishop Dunbar (1518/9-32) gave the date of 1125, but many scholars do not now accept this for the actual move to Aberdeen. There is even more confusion between the 1131/2 and 1136/7 dates. Written in the Book of Deer is a charter which is signed by Nechtan, Bishop of Aberdeen, usually dated to 1131/2. The date of 1137 appears to come from a grant and confirmation to the church of the Blessed Virgin and St Machar, given by King David I to Bishop Nechtan.