Kirken har et langhus med et spinkelt tårn. Grundstenen blev nedlagt i I første halvdel af 1200-tallet af kampestenssyld. Den første stenkirke opførtes af munkesten, men kirken var dengang væsentlig kortere og smallere. I dag indgår en rest af den ældste nordmur i kirkens nuværende skib. 

I ca. år 1300 fandt den første store ombygning sted. Her blev skibet forhøjet og udvidet, da der opførtes en helt ny sydmur, og murene blev forlænget mod vest. Samtidig opførtes nordre våbenhus, der sikkert har været kvindeindgangen. I sognet omtales den også som tunboernes kirkedør. Det hedder sig, at for den tid sejlede tunboerne til Samsø og gik op over bakkerne til Nordby Kirke.

Senere i 1400-tallet fandt en større om- og tilbygning sted. Der tilføjedes tårn og sakristi, ligesom kirkerummet blev overhvælvet. Man forlængede først endnu engang skibets ydermure mod vest.

Kirkens sakristi, der ved opførelsen var et meget smukt overhvælvet rum, stammer også fra denne byggeperiode, og var færdigt i år 1494. Nordby Kirke må herefter betegnes som romansk-gotisk.

Allerede først i 1500-tallet var der igen byggearbejder i gang ved kirken, hvilket blev afsluttet i 1531.

Det oprindelige loft blev fjernet i slutningen af 1800-tallet. Her blev kirkens oprindelige syddør frilagt, og det var også muligt at se, at kirken er opført i munkesten, idet her ikke er foretaget kalkning. Hvornår det blev vedtaget at kalke kirken udvendig vides ikke.

Kirkens nuværende vinduer er indsat omkring år 1880. På nordsiden af kirken anes tidligere vinduers udformning og placering.

I 1917 opførtes på arealet uden for kirkegården en såkaldt kirkestald. I dag rummer bygningen foruden kirkens oliefyr et redskabsrum, toiletter og mandskabsrum for kirkegårdens personale.

Kirkegården er omgivet af en mur of marksten. Denne er øverst afsluttet med cement og hvidkalket. Hovedindgangen mod øst er gennem portalen, der har ganglåge og kørelåge.

På murens nordside længst mod øst er der en lille ganglåge. Denne blev førhen ofte benyttet af kirkegængere fra Nordby, da de kom til kirken ad den stadig eksisterende gamle kirkevej.

Kirkegården, hvoraf størstedelen ligger syd for kirken, er blevet udvidet et par gange, først i 1862 og senest i 1930.