Kirken er antagelig bygget omkring 1200. Af den oprindelige kirke er kun det indre af murene i kirkeskibet fra tårnet og op til omkring prædikestolen og muren ned mod tårnet tilbage. Tårnet blev bygget omkring 100 år senere. Der fortælles i Veksø mange gode historier om, hvorfor tårnet ikke er højere en det er, og hvorfor der i tårnet er muret kampesten ind mellem munkestenene.

I 1866 blev kirkens oprindelige kor revet ned. Kirken blev forlænget og et nyt kor blev bygget. Ved samme lejlighed blev kirken udvendig beklædt med tynde granitkvadre. Indvendig blev murene pudset. Har der været kalkmalerier på væggene, er de antagelig blev ødelagt ved den lejlighed.

Det moderne krucifiks på nordvægen er udført af billedhuggeren Erik Heide.

I tårnet hænger to kirkeklokker. Den store er fra 1555 og har antagelig oprindelig hængt i et kirketårn på øen Øsel i Estland. Hvordan den er kommet til Veksø, ved ingen. Den lille klokke er støbt i Frederiksværk i 1801. Den by der ellers er kendt for på det tidspunkt at producere kanoner.