Vejby Kirke er i sin oprindelige skikkelse bygget ca 1100 som en stormandskirke i angelsaksisk-normannisk stil.

Det oprindelige tårn, hvis inderste del er skibets nuværende vestligste fag, har haft et herskabsgalleri hvilende på en midtersøjle med to buer. En rest heraf aner man indvendig i skibet over for indgangen til våbenhuset. Dette oprindelige tårn er tidligt blevet delvist nedrevet, og skibets tag er blevet ført hen over den underste tilbageblevne del af tårnet, således at enhver mindelse om dette tårn er forsvundet fra kirkens ydre, men spor heraf tydeligt ses i kirkens indre.

Bygningsmaterialet er sandsten, vistnok fra Hälsingborg-egnen. Som noget enestående i dansk kirkearkitektur er skibets mur indvendig og udvendig forsynet med en fremspringende 'kordon' gesims, som ikke findes på skibets senere østforlængelse, undtagen delvis på dennes nordside, formodentlig stammende fra materialer fra det oprindelige kor og den oprindelige apsis, som blev nedbrudt, da kirken forlængedes mod øst. Denne forlængelse fandt sted omkring år 1500, og midlerne hertil menes at stamme fra de mange offergaver, som valfarende til Helene Kilde og Grav lagde i kirkeblokken i Tisvilde, og som skulle fordeles mellem de syv kirkesogne, som nu udgør Helsinge Kommune.

Ved restaureringen i årene 1969-70 fandt man spor af det oprindelige kor, ligesom man fandt fundamenter til to sidealtre, som har været placeret ved overgangen fra det oprindelige skib til det oprindelige kor, ligesom man iøvrigt fandt det fundament, hvorpå ovennævnte midtersøjle i herskabsgalleriet har stået.

Det nuværende tårn er sandsynligvis kirkens yngste middelalderlige tilbygning. Den er skalmuret og på sydsiden forsynet med et trappehus, der formodentlig er en senere tilføjelse.

Våbenhuset på kirkens sydside er fra 1759 og afløste da et ældre våbenhus med højere rejsning. Fra våbenhuset fører en smuk og sjælden indgangsportal ind i selve kirken. Denne indgang har været benyttet indtil der i 1910 blev åbnet en anden indgang gennem tårnet. Den oprindelige indgangsportal danner rammen om en egetræsdør med følgende latinske indskrift oversat til dansk:"1556 gøres disse templets tærskler med døre for at modstå alle [djævle]klør". Dørringen er sikkert oprindelig, muligvis også låsen. Døren er et smukt eksempel på stilovergangen mellem gotik og renaissance. - Til højre for døren står en gammel pengeblok fra 1617.

Våbenhuset mod nord blev tidligt omdannet til materialhus, men er siden 1888 brugt som ligkapel.

Alterbordets renæssance-panelværker er ført tilbage til den oprindelige skikkelse fra 1599. Altertavlen stammer ligeledes fra 1599 og er bevilget og gjort - som der står på den med gamle gotiske bogstaver - da Ditlev Holck var høvedsmand på Kronborg. I midterfeltet sad tidligere en træplade, hvorpå Fadervor og indstiftelsesordene fra Skærtorsdag aften er malet. Nu er denne træplade erstattet af et maleri fra 1909 af T. E. Rannow. Altertavlens midterfelt er nu ophængt på korets nordvæg. Ved restaureringen i 1969 er såvel altertavlen som prædikestol og stolerader blevet malet med helt nye farver.

Prædikestolen en antagelig fra samme værksted som altertavlen. Den er i renæssancestil med fem fag. I de fire første fag findes relieffer af de fire evangelister. I det femte fag er der et relief af Paulus.

På skibets nordvæg hænger tre malerier, som fra venstre forestiller en af sognets præster: L[aurits] S[ørensen] og dennes hustru: D[orothes] M[athias] D[atter Vessel] samt en anden af kirkens præster: Arnoldus Hamermüller. De to første malerier er fra 1652, det sidste fra 1684.

Præstetavlen, som tidligere hang i kirken, hvor kalkmalerierne nu er afdækkede, hænger nu i tårnrummet. Døbefonten er af granit og firkløverformet med relieffer. Dåbsfadet er fra 1829 og forsynet med Frederik den Sjettes monogram i bunden, mens der på kanten står Weibye 1829. Dåbskanden, der ligesom dåbsfadet er af tin, bærer samme inskription.

Stolestaderne er barok og fremstillet af Christian Snedker i Hillerød i 1631. Hvor mange, der er oprindelige og hvor mange der er fornyede, kan vanskeligt afgøres. Bænkene er malet i 1998 med ny farvesætning af Poul Andersen.
Mellem de to øverste stolestader er der indbygget en præstestol nord for gangen og en degnestol mod syd.

Ved restaureringen i 1969-70 afdækkedes i en tilmuret vinduesniche på skibets nordvæg to lag kalkmalerier, som er aftrukket og hengemt på Nationalmuseet, er fra ca 1475 og forestiller to kronede helgeninder med glorier. Det underste lag er fra 1100-tallet og forestiller en dekoration i form af et bredt rødbrunt bånd omslynget af et lyst bånd. Denne form for dekoration har man - efter udsagn fra en ekspert fra Nationalmuseet - ikke fundet magen til i Danmark, men i Skåne, hvilket i og for sig ikke er så mærkeligt, da kirken er bygget af skånske sandsten. Foruden dekorationen i vinduesnichen er der på væggen omkring nichen fundet rester af kalkmalerier forestillende personer, som ikke kan identificeres.

Krucifixet, som sikkert er et oprindeligt korbuekrucifix, hænger nu over den gamle udgang gennem våbenhuset. Det stammer fra sidste fjerdedel af 1400-tallet og er ved restaurering blevet afætset.