Døstrup Kirke er en typisk romansk kvaderstenskirke fra ca. 1200 og bestod oprindeligt kun af kor og skib. Våbenhuset blev opført i 1880 og tårnet er rejst 1944 - bekostet af uddeler Niels Hvorslev og tegnet af kgl. bygningsinspektør E. Packness, Aalborg.
Norddøren er nu tilmuret, men portalen af to mandshøje granitsten pryder kirkens nordmur. En tærskelsten ligger ved kirken. Syddøren, der er i brug, har høje karmsten med svære rundstave, der fortsætter på en tympanon, hvis felt tvedeles af en lav, lodret rundstav. Et oprindeligt vindue i nordsiden er stadig i brug. Både korets og skibets vægge divergerer stærkt opefter. Over korbuens top er der en kalkmalet karvsnittet stjerne og på buefladen er der omkr. 1600 malet en bladornamentik, der "på forbløffende vis foregriber Bindesbølls stil".
Altertavlen er en smuk arv fra renæssancen, men i 1702 var den kommet i forfald og blev malet om med rødt og grønt samt gråviolette og gulgrå toner. Allerede i 1738 blev tavlen malet på ny, og på topstykket maledes et groft billede af opstandelsen. Senere er tavlen igen blevet "behandlet" et par gange, inden den i 1926 blev grundigt istandsat af maler Frode Nielsen efter Nationalmuseets anvisninger. I det store felt blev indsat en kopi af nadverbilledet på altertavlen i Tranebjerg kirke pa Samsø. Prædikestolen er et smukt snedkerarbejde i egetræ, udført i den gedigne renæssancestil fra 1600-tallet.
Den romanske granitfont er af vestjysk type med glat, attisk profileret kumme på en fod, formet som et klo-kapitæl.