The earliest existing historical records of the church date back to the year 1308, but the church was not new at that time. The first church in Olden was a wooden stave church that was likely built during the 13th century. The church had a long church design with a nave that measured about 11 by 7 metres (36 ft × 23 ft) and a choir that measured about 6 by 7 metres (20 ft × 23 ft). In 1723, the church was purchased by Peder Pederson Tonning, who bought the church at the Norwegian church auction which was set up so the King could pay off debts incurred from the Great Northern War. In 1746, the old stave church was torn down and then a new timber-framed long church was built on the site. In a severe winter storm in 1757, the church was heavily damaged. That spring the church was torn down and a new building with a cruciform or Greek Cross design was completed in 1759. It is not known who designed the building, but the lead builder was Jon Langeland. The building had a choir in the eastern cross-arm with a sacristy on the end of it and it has a church porch on the west end of the building. Each of the cross-arms measures about 6 by 6 metres (20 ft × 20 ft) and there is a 6-by-6-metre (20 ft × 20 ft) square in the center which connected all four cross-arms. The church was consecrated in 1759.^[5][6][7]

In 1893, the Tonning family (who had owned the church for over 150 years) sold the church to the parish. By this time, the old church had been deemed to be too small for the congregation. Discussions were held on whether or not to renovate, expand, or replace the old church. The Norwegian Directorate for Cultural Heritage and the Society for the Preservation of Ancient Norwegian Monuments both participated in the debate on the matter. In 1933, it was decided to build a new church on a nearby site and to keep the old church as a museum. In 1934, the new Olden Church was built to replace this church. The new church was consecrated on 19 December 1934. After this, the old church was taken out of regular use and renamed Old Olden Church. Since then, the church has been used occasionally for special services, but it is open to tourists during the summers. In 1969, there was a major restoration of the church building. The Old Olden Church is no longer used as parish church but remains a tourist destination.^[5][6][7]

Religious paintings and statues are featured in the church. Displays include a Holy Bible which dated from the reign of King Christian III of Denmark. In 2016, the Norwegian Institute for Cultural Heritage Research undertook a complete restoration of the altarpiece in the church.^[8]

• List of churches in Bjørgvin