The earliest existing historical records of the church date back to the year 1457, but the church was not new that year. The first church in Eide was probably a stave church that was possibly built during the late 13th century. In the late-1500s or early-1600s, the old stave church was torn down and replaced with a new church building. Not much is known about that church.[3][4]
In 1795, the old church was torn down because it was getting too small for the congregation as well as some worsening structural problems. After its demolition, a new cruciform church was constructed in the same location, although it was moved slightly to the south (this is known because some skeletons were found under the current church during some excavations and renovations, meaning it was built over what was once part of the cemetery). In 1796, the church was mostly completed and the congregation began to use it at that time. In 1798, the exterior walls were covered with siding and small projects continued to be finished over time, meaning the church was not officially completed until 1806. The church was formally consecrate on 17 July 1825.[3][4][5]