The earliest existing historical records of the church date back to the 1100s, where it is written about in the Icelandic Rimbegla which states that "Lenvik Church, just south of the Malangen, is the northernmost church in the world" (fyrir sunnan Malangr stendr kirkja, er heitir í Lengjuvík, er menn hyggja norðasta kirkju i heiminum). The old church site was located near the confluence of the Malangen Fjord and the Gisundet strait, about 12 kilometres (7.5 mi) north of the present church site. During an attack by the Karelians in 1386, the rectory by the church was said to have been burned, but there is no record that the church was also burned. In the year 1700, an old church was torn down on the site and a new church was built on the same site to replace it. It was a timber-framedcruciform building with a low roof line. Around 1776, the church was renovated and a sacristy was built on the east end of the building.[4]
In 1814, this church served as an election church (Norwegian: valgkirke).[citation needed] Together with more than 300 other parish churches across Norway, it was a polling station for elections to the 1814 Norwegian Constituent Assembly which wrote the Constitution of Norway. This was Norway's first national elections. Each church parish was a constituency that elected people called "electors" who later met together in each county to elect the representatives for the assembly that was to meet at Eidsvoll Manor later that year.[5]
In 1820, the church was demolished and a new one erected on the same site. This new church was a timber-framed building with an octagonal floor plan and by 1822, the church was already in need of repairs. The second floor seating balcony had structural deficiencies and needed repair. The local climate also affected the church and due to tight finances, the church often postponed regular maintenance on the building, which led to a deterioration of the building.[4]
In a January 1874 meeting of the municipal council, the question came up about the location of the church. The parish boundaries had recently changed and the church was no longer central to the municipality. The council decided to move the church to Bjorelvnes, about 12 kilometres (7.5 mi) further south along the Gisundet strait. In September 1874, the council decided to dismantle the old church and reuse the same materials to build the new church. Over the winter, the Diocese told the council that the new church must have seating for at least 700 people, so the new church had to be larger and the old materials would not be enough. After some negotiation with the diocese, in May 1875, the council approved building a brand new Lenvik Church at Bjorelvnes and the materials from the old church would be moved to Rossfjordstraumen where they were used to build the new Rossfjord Church. In 1879, the new Lenvik Church was built at Bjorelvnes as the old church was taken down in 1885 and its materials were used to build the new Rossfjord Church.[6][7]
