Vidstrup Kirke er opført omkring år 1150, og er sammen med Tornby en af de ældste romanske kampestenskirker i Vendsyssel. Kirken består af kor og skib og har aldrig haft et tårn. Det kan ses, at kirken tidligere har været sat om, da mange af kvadrene på kirkens sydside, vestgavl og kor-gavl ikke længere er på deres oprindelige plads. Kirken blev bygget med tre vinduer i koret, der senere er muret til. I gavlen kan man se svage spor af det midterste.

Alteret Det oprindelige romanske alterbord blev fjernet i begyndelsen af 1800-tallet og erstattet med et nyt og mindre, der blev muret i teglsten Det gamle alterbords dæk plade hænger i dag i våbenhuset. Den har et hul med fals til et relikviegemme. Et nyt altertæppe blev indviet i 1994. Altertæppet udformning og farvevalg blev lavet til kirken af kunstner Kaj Nørkjær. Året efter blev en ny alterdug indviet. Den er kniplet og monteret af Anna Christensen i 1995.

Altertavlen er en lutheransk fløjaltertavle fra slutningen af 1500-tallet. Den består af et midterskab med to bevægelige fløje (triptykon) Topstykkerne på hovedstykket og fløjene er tilføjet i anden halvdel af 1700-tallet. Billedet er en kopi af C. Blochs altertavle i Holbæk Kirke: Kristus velsigner et barn, og opsat i 1935. Altertavlen bærer følgende indskrifter:

Venstre topstykke: »Ære være Gud«

Midterste topstykke: »JAHVE« - det hebraiske navn for Gud.

Højre topstykke: »I det højeste«.

Venstre sidefløj: »Vor herre Jesus Kristus i den Nat, der hand blev forraadt tog hand Brødet Takkede og brød det - gaf sine Disciple og sagde: tager dette og æder det - det er mit Legem som givis for eder til min Ihukommelse. Ligesaa tog Hand og Kalchen efter Aftens-Maaltidet Tachede gaf dennem og sagde: Drick alle deraf. Denne er det Nye Testamentis Kalch i mit Blod som udgydes for eder til Syndernis Forladelse. Dette gjører så ofte som I det driche til min Ihukommelse.«

Højre sidefløj: »Fader vor du som er i Himlene, Helliget vorde dit Nafn tilkomme dit Rige Skee dinVilje som i Himlene saa og paa Jorden - Gif os idag vort daglige brød og forlad os vor Skyld som vi forlade vore Skyldnere. Leed os iche udi Fristelse men frie os fra det Onde. Thi Riget er dit Magten og Æren i Ævighed Amen.«

Forneden i midten på altertavlen står der: »1. Cor. XIV V21: Thi saa ofte som I æde dette Brød og driche denne Kalch forkynder Herrens Død indtil hand kommer«. Forneden til venstre ses bogstaverne: »N K«(Niels Kjær)

Forneden til højre: »K de H« (Karen de Hemmer)

Karen de Hemmer var i 1700-tallet først gift med præsten, magister Jens Wang, og efter dennes død med Niels Kjær i Kjærsgård, som var ejer af både Vidstrup og Tornby Kirker.

Døbefonten Romansk døbefont af granit og uden ornamenter og stammer utvivlsomt fra kirkens ældste tid. Kummen er glat og halvkugleformet.

Foden er en terningkapitæl, som er karakteristisk for Vendsyssel. Se links under

Dåbsfadet er fra 1700-tallet og glat.

Over korbuen er der et lille udsnit af et kalkmaleri, der blandt andet er nævnt i en indberetning National Muset i 1885. Det blev genopdaget, da kirken blev restaureret i 1961. Udsnittet, der kan ses den dag i dag forestiller en due. Hele kalkmaleriet, der forestillede agterstavnen af et skib, måske Noas Ark, stod ifølge Nationalmuseet ikke til at redde.

Kirkeskibet er en model af Fregatten Jylland og er bygget ud af et industrielt fremstillet byggesæt. Det blev hængt op den 1. søndag i advent

Orglet er bygget af Bruno Christensen i 1981 og er seks stemmigt. Det er farvegivet, ligesom kirkebænkene, efter kunstner Kaj Nørgaards anvisninger

Prædikestolen er fra 1696 og er udskåret i egetræ, og hviler på et nyere understel. Oprindeligt var prædikestolen malet men blev siden renset for malerrester. Lydhimlen over stolen er også i egetræ.

Prædikestolen er blandt andet en marguerit med 10 kronblade. Bladene er symbolet på de 10 bud og samme marguerit har Kaj Nørkjær gengivet i sit altertæppe fra 1994.

Kirkeklokken, kan dateres til 1150. På klokkens nordside er der et ligeartet kors dannet af fine linjer. Klokken var i mange år hængt i en stabel ved kirkens vestende, men blev omkring 1930 flyttet til kirkegården novedvestlige hjørne i et klokketårn.

I 2015 fik kirken en ny klokken en ny klokke ved siden af den gamle. Skænket af A. P. Møller og hustru Chastine McKinney-Møllers fond til almene formål. Den er støbt af Olsen Nauen klokkestøber i Norge og bærer inskriptionen: Mens året går og vinden bider, lyder Herrens ord i nye tider”.

Restaurering: Vidstrup Krike gennemgik i 1961 en omfattende restaurering. Gulvhøjden blev sænket overalt og lofterne fornyet, så bjælkerne trådte tydeligt frem. I forbindelse med restaureringen fandt man et lille granitkors ornamenteret med en tovsnonig og et diagonalt kryds. Korset kan ses ved kirkens vestgavl omtrent der, hvor klokkestablen stod