The earliest existing historical records of a chapel at Fedje date back to the year 1636, but the chapel was not built that year. The first chapel was a small wooden building that was possibly built during the 14th century (in the mid-1600s, it was described as being very old). The chapel was an annex chapel within the large Lindaasprestegjeld. Shortly after the last worship service on 24 April 1659, the old chapel was torn down and on 21 August of the same year, the new church was consecrated as the first official church on Fedje. The church was not much larger than the chapel on the site—the nave was only 8 metres (26 ft) long. Extensive repairs were carried out around the year 1800. Again in 1869, the church got a new floor and three new windows.[2][3]
After two major repairs during the 1800s, the church was still in poor condition by the 1880s, so it was decided to replace the church. After a fundraising campaign, the old church was demolished in 1888 and a small wooden church was built. The new building was designed by an architect named Norøen and Peder Gabrielsen Spjutøy was the lead builder. The nave was 10.3 by 7.36 metres (33.8 ft × 24.1 ft), the chancel was 3.98 by 3.90 metres (13.1 ft × 12.8 ft), the church porch under the tower was 1.48 by 2.74 metres (4 ft 10 in × 9 ft 0 in), and the sacristy measured 3.2 by 1.59 metres (10.5 ft × 5.2 ft). The church had 78 seats. This new church was consecrated by Bishop Waldemar Hvoslef on 17 October 1888. The new church, however, quickly became too small for the congregation. By 1918, the parishioners began a plan to finance a new and larger church.[2][3]
By the late 1930s, plans were underway to replace the small church. Ole Halvorson, from Bergen, was hired to design the new church and a builder named Lunde was hired to lead the construction. Site work began in 1937 and in 1939 the old church was torn down. Construction on the new church began right away in 1939, but unfortunately the start of World War II and the Invasion of Norway delayed the completion of the new church. It was not until 1941 that the church was finished and on 7 September 1941 it was consecrated by the Bishop Andreas Fleischer.[2][3]