There has been a church on the island of Fjelbergøya since the Middle Ages. The earliest existing historical records of the church date to the year 1561, but it was in use before that time. That first church was a wooden stave church that was likely built during the 13th century. In 1618, the church was renovated and it got a new floor, new windows, and a new pulpit. In 1627–1629, the church got a new tower. In 1638, the church porch was rebuilt. In 1721, the church was described as "an old and decrepit stave church where there is great danger to its life, especially when the wind blows hard" (Norwegian: Een gammel og i Grund forraadnet Stave Kirche, hvor udj Tienisten med allerstørste LifsFare forettes, og i sær naar det blæser Noget hart). Due to its poor condition, the church was torn down in 1722 and replaced by a new timber-framed long church, about 5 to 10 metres (16 to 33 ft) further to the west of where the old church stood.^[3][4]

In 1814, this church served as an election church (Norwegian: valgkirke).^[5][6] Together with more than 300 other parish churches across Norway, it was a polling station for elections to the 1814 Norwegian Constituent Assembly which wrote the Constitution of Norway. This was Norway's first national elections. Each church parish was a constituency that elected people called "electors" who later met together in each county to elect the representatives for the assembly that was to meet in Eidsvoll later that year.^[5][7]

In 1862, there was discussion of replacing the church, but instead it was decided to simply refurbish the old church. The chancel floor was raised up, new windows were installed, and the chancel arch was replaced. Another renovation was completed in 1939 which included removing the second floor seating gallery along the north wall of the nave. In 1969, a sacristy was built on the east side of the choir.^[3]

• List of churches in Bjørgvin