The Romanesque stone church has a rectangular nave and a narrower, almost square chancel where the width is greater than the length. In a first construction phase, the choir and the first 1 metre (3 ft 3 in) or so of the eastern part of the nave were built using locally sourced soapstone. In the next phase, the rest of the nave was completed. During archaeological excavations under the church, no evidence was found for any previous churches on this site.[4]
From 1863 to 1865, the western portion of the old nave was torn down and a new, longer and wider nave was rebuilt on the same site. A new tower on the west end was also constructed. This renovation and expansion was led by the architect Niels Stockfleth Darre Eckhoff. The new addition became the nave, the part of the old nave that remained was converted into a choir, and the old choir was converted in to a sacristy.[4][5]
In the 1920s, the oldest choir was partially restored to its old form. A thorough restoration was begun in the late 1960s. The original sections were partly restored to their former appearance with smaller windows and steeper roof angles. The new nave from the 1860s got a shape and appearance reminiscent of the old nave. The west tower was removed and the church again got an onion dome over the roof ridge to the west. The church was reopened after the restoration on 21 June 1970.[5]
Helgeland Kammerkor, a mixed choir from the district of Helgeland, used Alstahaug Church as the venue for a recording of folk music from Helgeland (Folketoner fra Helgeland, 2005). The album contains 27 folk tunes from Helgeland, recorded in collaboration with folk musicians from the area.