Studies have shown that Herøy Church has a complicated building history. During the Middle Ages, the church was the only one in Northern Norway to have a choir with an apse (a rounded recess at one end of the choir). The choir was built first, abutting an older wooden church that stood there at that time. When the wooden church was removed, the apse was added to the east and a church nave to the west. During the Late Middle Ages, the nave fell into disrepair and was shortened by about a third. Thus the church remained until 1879, when the nave was extended to twice its length and the west tower was erected as well.

The church was inspected and restored in around 1960 under the guidance of architect Håkon Christie, who has set up the building phases shown in the scale drawing.

The drawing is taken from Ekroll, Eystein: Med kleber og kalk. Norsk steinbygging i mellomalderen, Oslo 1997, page 297.