Nordby Kirke er opført af bygmester Peder Frisvad som afløser for sognets gamle kirke, der lå i Rindby ca. 2 km længere mod syd. Den rektangulære og klassicistiske bygning, der ved opførelsen kunne rumme 700 kirkegængere, er opført af mørkbrændte mursten i blank mur og dækkes af helvalmet tag. Kirken er vanen tro øst-vest-orienteret med to mindre udbygninger i nord og syd, der rummer hhv. våbenhus og sakristi. Facaderne i øst og vest smykkes hver af en midtrisalit med frontispice, den østre dog skjult af en tilbygning fra 1906, nu med funktion af dåbsværelse. Samme år blev den oprindelige tagrytter udskiftet med det nuværende, større eksemplar.
I det indre er alteret på utraditionel vis placeret midt for den søndre langside, og kirkens indretning udgør dermed en af landets få bevarede prædikensale fra 1700-tallet. Dele af inventaret stammer fra forgængeren, herunder det ældste stykke, malmdøbefonten fra 1400-tallets sidste halvdel. Det maritime tilhørsforhold understreges af kirkens mange kirkeskibe, nu ni i alt, der er fremstillet i tiden fra ca. år 1700 og frem til 1966. Dermed repræsenterer de næsten alle perioder i landets kirkeskibstradition.
