Kirken er bygget af granit- og teglsten. Skibet og koret er tækket med bly. Tårnet fra 1949 og med tegltag.
Den store gravhøj på kirkegården appellerer til fantasien. Man ved, at graveren er stødt på meget store sten, så måske gemmer højen en dysse eller jættestue fra stenalderen.
Emil Nolde har malet kirkens alterbillede "Middag i Emmaus" malet i 1904. Billedet der var vurderet til mindst 10 mio blev stjålet i marts 2014. I 2018 blev maleriet fundet i Slesvig-Holsten og afleveret til det danske politi. Nationalmuseet restaurerede maleriet og den 1. december 2019 blev det genindviet i kirken.
Efter Nolde-maleriets forsvinden fra Ølstrup Kirke er en ny altertavle nu blevet indviet. Det skete ved gudstjenesten den sidste søndag i juni 2014. Den nye altertavle er malet af en af sognets egne beboere, Alice Ravnholt.
