Den oprindelige kirke har været en lille, senromansk teglstenskirke, hvis murværk delvist er bevaret i den nuværende kirkes ældste del, dvs. de to fag af skibet der støder op til det langt senere opførte vesttårn.
Hals Kirke er opført i ca. år 1200. Den er siden da blevet ombygget og udvidet op til flere gange. Den seneste restaurering fandt sted fra 1960-65. Den gamle kirke danner i dag rammen om gudstjenester, koncerter, minikonfirmandundervisning og meget mere.
Kirkebygningen i Hals
Kirken består af et imponerende flot langhus med skib og kor i ét. I den vestlige ende er tårnet og på sydsiden en tilbygning samt våbenhus. Det menes, at den ældste del af kirken er de to vestligste fag af skibet, som oprindeligt stammer fra senromask tid, men er så ombygget, at det er svært at finde spor af den oprindelige bygning.
I kirken findes bl.a. en døbefont i granit. Døbefonten er kirkens ældste inventar, og er endog ældre end selve kirken. Dette faktum åbner for to fortolkningsmuligheder; enten må døbefonten været lavet til en anden og ældre kirke i Hals, eller også må den været bragt hertil fra en romansk kirke, beliggende i omegnen af Randers, hvor man finder denne type døbefont.