The earliest existing historical records of the church date back to 1432, but the church was not new that year. The first church in Hjørundfjord was a wooden stave church that was originally located at Hustad, about 700 metres (2,300 ft) southwest of the present church site in Sæbø. The old stave church was possibly built during the 14th century. In the mid-1500s, the church was damaged in an avalanche from the nearby mountain. In 1581, there was some flooding and changes to the flow of the small river that passed by the church which caused major damage. After this, it was decided to dismantle the church and move it 700 metres (2,300 ft) to the northeast into the village of Sæbø where it was rebuilt. The newly moved and rebuilt church was consecrated in 1584. In 1711-1713, the old stave church was expanded with the construction of a transept to the north and south of the nave which converted the long church into a cruciform design.[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]
Throughout the 1700s and 1800s, the church was in fairly regular need of repairs and expansion. By the 1860s, the it had become clear that the church needed to be replaced. At that time, the ownership of the church was divided among several people in a collective and this delayed the replacement process. In 1877, the church was purchased by the municipality and work on a new church began soon after. Henrik Nissen was hired to design the new church. In 1880, the new church was built about 40 metres (130 ft) to the west of the previous location. The lead builder was Carl Berg, who allegedly went bankrupt along the way and had to stop his work. After this, the church was completed by Johan Olsen. The new building was consecrated on 11 September 1880. After the new building was completed, the old church was torn down.[4][8]