The first churches in the county of Finnmark were built along the coast. People living in the inland were only infrequently in contact with the church and its teachings. The pietist, Lutheran vicar and missionary among the Sami population, Thomas von Westen did in 1717 remark that there were few churches in the inner areas of eastern Finnmark. At the end of the 18th century Swedish clergymen would also visit the border areas.

A donation of 400 speciedaler (the Norwegian currency between 1816 and 1875) was made by the "Nordlanske Kirke- og Skolefond" (an organisation set up in 1715 to fund evangelization among the Sami population) to the municipality of Tana to build Polmak Church and permission to build was granted in 1847. The church was consecrated in 1853 by the dean Søren Christian Sommerfelt who declared the church a light, fine and friendly house of God. He was also of the opinion that it was large enough to serve the local resident population as well as the part of the Sami population that lived a nomadic way of life. The timber used was floated down the river from the Karasjok area and the church did not get external cladding until 1859. Originally the roof was covered in wooden shingles.