The earliest existing historical records of the church date back to the year 1350, but it was not new that year. There has been a chapel on the island of Utvær from the 12th century until the early 18th century. It was a part of the great parish of Evindvig. There were only a few services per year at that chapel, and it was difficult to get to in the winter. The chapel was dedicated to St. Clement, the patron saint of mariners. Legend has it that King Harald Hardråde gathered his fleet at Utvær before sailing to attack England in 1066. The weather on Utvær was harsh and the chapel sat on a high point, very visible on the relatively flat, rocky islands. There are reports of the roof being blown off the chapel and the siding being repaired. In 1666, Scottish seafarers raided the chapel and broke some windows. Reports from 1686 tell that Utvær chapel had a nave that measured and a square choir that measured on each side. The last service held at Utvær was on 1 August 1717. After that, the church was torn down and replaced with a new church on the small island of Husøy, a little closer to the mainland. The new chapel was built in the fall of 1717 or the spring of 1718 on the small island of Husøy, just west of the large island of Ytre Sula. It was a small white church with its nave measuring with a low steeple. The new church could seat about 120 people. The church site was not the greatest. By 1755, the church records show that the wooden beams supporting the floor were already rotting. Also, there was very little soil on the rocky island, so it was very difficult to bury coffins in the churchyard. In 1787, the church was repaired with the hopes that it would last another 100 years. During the 1800s, the area had increased in population so that the congregation was nearly 500 people. In 1888, Husøy was split out from the vast Eivindvigprestegjeld, becoming a parish of its own, with Husøy Church being the only church to serve the new parish. It was eventually decided to move the church again. It was moved to the village of Kolgrov on the western coast of Ytre Sula island. Construction of the new building began in the spring of 1896. When the new church was completed, the old church on Husøy was sold and torn down. The materials were used to build a prayer house in Leirvåg in Lindås.
