Haljalassa oli kirkko jo 1200-luvulla. Nykyinen kivikirkko rakennettiin puisen sijaan 1300-luvun lopussa. Torni sai nykyasunsa 1860-luvulla, mutta tornia on jo varhain käytetty vahtipaikkana, mikä paljastuu tähystys- ja ampuma-aukoista tornin sivuilla.

Haljalan kirkko sai urut ainakin vuonna 1852 (Gustav Normann). Näiden urkujen kunnosta ei tämän kirjoittajalla ole tietoa, mutta seurakunta osti Väike-Maarjan seurakunnalta sen toiset urut jouluksi 2006. Saman vuoden keväällä Väike-Maarjan kirkon vanhat urut, niin ikään Normannin rakentamat, oli saatu restauroiduksi, joten seurakunta luopui 1990-luvulla hankitusta Walckerin rakentamon kuoriuruista ja myi ne Haljalaan.

Haljalan kyläkirkoissa, Käsmussa ja Ilumäessä, on melkoisia urkuharvinaisuuksia.