By 1726 the fabric of the church was ruinous. Latterly it was used as a dwelling house and in 1855 Henry Dryden described what was left of the church itself, which included the S doorway and aumbry, and remains of a stoup or piscina. The pre-Reformation, on-site doorway seems to have been moved to its present location by John Reid, who bought the property. By 1896, the building was being used as a carpenter’s shop and warehouse.

The Norwegian King Olaf II was killed at the Battle of Stiklestad (Norway) in 1030 and was canonised locally soon afterwards. St Ola’s Church is the first known church to have been built in Kirkwall and it has been suggested it might have been built by Earl Rognvald Brusason, who had a residence in Kirkwall in the mid-11thc. Rognvald, a foster son and keen supporter of Olaf, became joint Earl of Orkney about 1037 and died 1046. The first reference to Kirkwall, which means ‘church bay’ or 'creek of the kirk', comes in the Orkneyinga Saga in its narration about Rognvald Brusason. Rognvald, himself, was buried in Papa Westray (Orkney). Another suggestion is that a dedication to St Olaf may have been made at a later date, at the time of Olaf’s son Magnus Barelegs, who seized power over the Orkney Islands c.1100. Walter Havyck ‘persone of Sant Olave Kirk’ appears as a witness in a disposition of 1481. Rognvald became joint Jarl (Earl) of Orkney about 1037 and died in 1045/6. According to Jo. Ben, writing about 1529, St Ola’s church was reduced to ashes by the English. This appears to have taken place in the early 16thc. Bishop Robert Reid (1540 until the Reformation) rebuilt the church.

The first churches dedicated to St Olaf in England appear to be no earlier than the mid-11thc, as in London and York. Kirkwall was a Norwegian territory and became part of the archdiocese of Trondheim/Nidaros in the 1150s. Until the construction of the cathedral church of St Magnus, St Ola’s church may have been the main (and possibly only) church in Kirkwall.