Ifølge Nationalmuseets bog om Danmarks Kirker er Grimstrup og Vester Nykirke opført omtrent samtidigt samtidigt omkring år 1100,
måske oven i købet af samme stenmester. De er begge opført af kampstenskvadre med et helt smalt og langsrakt skib og forholdsvis kort kor skib og absis våbenhus er tilføjet i middelalderen og senest Tårnet.Bortset fra enkelte reguleringer sidder vinduerne på deres oprindelige pladser
Syddøren har været tilmuret med granatkvidre siden 1886.
Hele kirken fik en hovedrestaurering i 1951-52, hvor blytaget blev fornyet og vinduerne fik nye rammer. Kvadrestensmurene blev omsat, og der blev lagt nyt teglstensgulv.