The white, wooden church was built in a octagonal design in 1838 by Anders Thorsen Syrtveit using plans drawn up by the famous architect Hans Linstow.

The first church in Hylestad was the Hylestad Stave Church which was located at Kyrkjemo in the Bjørgum farm area on the east side of the river Otra, about 900 metres (3,000 ft) to the northwest of the present church site (on the west side of the river).

Since the majority of the municipal residents lived on the west side and the newly constructed road through Valle (now Norwegian National Road 9) was also built on the west side of the river, it was decided that the new church would also be built on the west side, right alongside the road.

So the old church was torn down and the new one was built at Rysstad about 900 metres (3,000 ft) to the southeast of the old site.

Some of the items from the old church such as the churchyard wall and the main gate were transported across the river ice during the winter from the old church site to the new site.