King Sigurd of Norway is said to have converted Orkney around 996 AD, but it does not appear to have come under the control of the Roman church until the time of Adalbert, Archbishop of Hamburg (1043-72) In 1152/3, Nidaros (Trondheim) became an archbishopric and Orkney came under its ecclesiastical control. Thorkel Amundson, foster father of Thorfinn Sigurdsson (The Mighty) had a homestead in Deerness. According to the Orkneyinga saga Thorkel killed Rognvald in 1046. Excavations have uncovered a Viking settlement a short distance of the medieval church at Skaill in Deerness.

The medieval parish church was taken down and rebuilt in late 1790s. The present church is the 1790s church, remodelled in the 20th century and by now is owned by "The Friends of St Ninian’s", formed in 2009 to save this church.