Hallenslev Kirke er fra 1100-tallets første del.
Den oprindelige kirkebygning bestod af skibet og koret, som er opført af rå og kløvede marksten i romansk stil.
I 1400-talletet blev tilføjet sakristi og våbenhus.

Kirkens tårn er fra 1400-tallet. Den nederste tredjedel er opført af marksten, resten er af munkesten.
Kirkens har to klokker, den ene er fra 1613, den anden blev omstøbt i 1868.

Det store nordkapel er opført omkring 1525, men kapellet nåede sandsynligvis ikke at blive færdiggjort inden reformationen. Oprindelig har kapellet være forbundet med skibet gennem en bred arkade på den gamle kvindedørs plads. Denne arkade er forlængst tilmuret.
Døren i gavlen, de tilgitrede vinduer og den tilmurede arkade skyldes muligvis, at bygningen har tjent som opbevaringssted for tiendekorn. Siden 1862 har bygningen været benyttet som materialehus.

Prædikestolen er fra 1648.
Et flot træskærerarbejde, hvis sider er inddelt i fire felter med evangelisterne Mattæus, Markus, Lukas og Johannes.

Døbefonten, der er fra slutningen af 1200-tallet, er fremstillet af gotlandsk kalksten.
På døbefonten er bevaret rester af den oprindelige rød-brunlige maling.

I 1571 flyttede kirkeejer Waldemar Hvidt døbefonten til sin have på Frihedslund og anbragte i stedet en døbefont af cement i kirken. I 1940 blev den ført tilbage til sin oprindelige plads i kirken.