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-aisle 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. From the outside, the facades remained smooth, pierced only with pointed, high windows and an entrance portal on the south side.