Biserica parohială cu hramul „Nașterea Maicii Domnului” a fost construită între anii 1755-1757 din piatră de râu cu mortar de var, prin strădania ctitorilor: Andrei Iacobovici, soția acestuia Maria, cneazul Ștefan Pârva împreună cu hălmăgenii și leștiorenii. Mormintele ctitorilor se află în interiorul bisericii (intrare bărbați stânga și naos sub fereastra de nord). Biserica este construită în stil baroc având dimensiunile de 31/12 m. Frumoasa pictură în frescă de pe pereți, cât și de pe tâmplă, a fost executată în anul 1768 de către zugravii Gheorghe și Radu Zugravu, după cum arată inscripția de la proscomidiar.

În anul 1867 biserica a suferit unele transformări: pereții au fost ridicați cu cca. 80 de cm. Ușile și ferestrele au fost mărite, iar prin distrugerea bolții a fost distrusă și pictura ce exista pe ea. Tot atunci s-a construit și un balcon deasupra pronaosului, afectându-se și o altă parte din pictură. În acestă situație, pentru a acoperi stricăciunile, s-a tencuit toată suprafața interioară, iar peste pictura originală de pe tâmplă s-a suprapus o altă pictură, în ulei, realizată de pictorul Ioan Demetrovici din Timișoara.

Inițial biserica a fost acoperită cu șindrilă, iar turnul cu tablă. În anul 1896, acoperișul din șindrilă a fost înlocuit cu tablă.

În anul 1967 s-a hotărât pictarea bisericii și cu această ocazie s-a descoperit existența unei picturi de valoare ce a fost acoperită cu mortar în anul 1867. Direcția Monumentelor Istorice în colaborare cu Departamentul Cultelor, a organizat scoaterea de sub tencuială a picturii, cu valoare aristică și culturală deosebită, pictorii fiind unii cu renume în epocă, mai ales Radu Zugravu (el și ucenicii săi pictând biserica din Gura Văii-Vâlcea, schitul Brădet-Argeș, schitul Cornet-Vâlcea și scene din viața Cuvioasei Filofteia de la Curtea de Argeș).

Cea mai reușită pictură a lui Gheorghe și Radu este Judecata de Apoi de pe peretele de apus al bisericii din Hălmagiu, după cum precizează profesorul V.Drăguț în lucrarea „Pictura românească în imagini” (București, 1976). Scoaterea de sub tencuială, dar păstrarea urmelor de buceardare din pereți, a fost executată de pictorul specialist Arutiun Avakian din București, în anul 1968. Tot atunci a fost demolat și balconul.

Între anii 1970-1971, au fost scoase în evidență formele vechilor ferestre și figuri de sfinți și cuvioși pictați între ferestre, care au fost de asemenea restaurate împreună cu pictura de pe tâmplă. Tot în această perioadă a fost pictată bolta bisericii în tempera și au fost completate spațiile libere care erau nepictate. Toate aceste lucrări au fost executate de pictorul restaurator Ieromonah Firmilian Gh. Ciobanu ajutat de pictorul Gheorghe Trășculescu, ambii din București.

Sfințirea bisericii a avut loc la 11 iulie 1971 de către episcopul Aradului, Ienopolei și Hălmagiului, Teoctist Arăpaș, viitorul patriarh al României, sub pastorația preotului Radu Bejan.