Højt og smukt ligger Kornum kirke på en stor, åben mark, som en ø i et hav, der skifter form og farve efter årstid og afgrøder. Den kan betragtes som en hedekirke.
Kirken ligger midt i en forblæst kirkegård, hvor de store træer karakteristisk hælder mod øst. Kirken er i dag uden tårn. Det fortælles, at en kone en dag så syv vildgæs, som hun ville fange med et reb. Hun fik dem bundet sammen, men blev så bjergtaget, at hun ikke kunne slippe rebet igen. Gæssene lettede, og fløj af sted med konen hængende i rebet. De fløj hen over Kornum kirke, hvor konen ramte tårnet, der derpå faldt sammen. Siden da har kirken ikke haft et tårn.
Kirken består af et romansk kor og skib, og i 1932 blev et våbenhus tilføjet på nordsiden. Den romanske bygning er bygget af granitkvadre på skråkantsokkel, og den retkantede norddør blev genåbnet i 1932.
Kirken er ukalket, med undtagelse af gavlene, våbenhuset, og den øverste kant under taget. De opskallede tagværker er fornyet i slutningen af 1700-tallet, antageligt 1795, da man nedrev et formentlig sengotisk vesttårn, hvis fundamenter og tilmurede tårnbue endnu spores. Våbenhuset blev rejst i 1932 ved arkitekt S. Vig-Nielsen. Inden dets opførelse var indgangen gennem en dør i vestgavlen med et lille vindfang.
Indvendig står den overgribende, runde korbue som et af de få oprindelige elementer. Buens kragsten er profilerede, og de løber mod vest. Buen, og kvaderstensvæggen den sidder i, adskiller koret og skibet.
Buens linier følger ikke kirkens linier helt nøjagtigt. Dette symboliserer, at kun Gud er i stand til at skabe det perfekte. Der er lave bjælkelofter i kor og skib.
Af oprindelige enkeltheder ses i øvrigt et tilmuret vindue på skibets nordside – det eneste, der har været her.