The first wooden church in Haljala was built in the thirteenth century. The erection of the present, stone temple took place in the years 1430-1440, while the church tower was added at the end of the 15th century. Church also had a defensive function, it is known that the weapons were stored in it. In 1558, the temple was damaged during the Livonian War, and in 1703 during the Northern War was burned by Russian soldiers. Another fire touched the building in 1831, destroying the tower and roof of the church. The reconstruction of the temple, that gave the present appearance, was carried out in 1865.
The church is a hall, three-nave structure, orientated towards the sides of the world. It consists of a rectangular nave, a narrower and shorter chancel ended by a straight wall and a 34-meter high tower on the west side.