Mejlby kirke består af romansk skib, kor og apsis. Tårnet fra 1957 er ligesom den øvrige del af kirken opført af granitkvadre, og er særpræget ved at den øverste del er åben, så klokkerne er synlige udefra. Norddøren med tympanon er bevaret i tilmuret stand, og den sydlige er med tympanon og karme indsat i tårnet som indgang til kirken.
Den foregående altertavle, et maleri af Jesus som den gode hyrde, er sammen med en endnu tidligere, tredelt altertavle med skriftsteder, ophængt i skibet. På Alterbordet ses nu et moderne krucifiks, som er opsat i forbindelse med en nylig restaurering.Døbefonten er en meget velbevaret romansk løvefont.

Kirken fremvises af graveren Søren Villesen, der normalt træffes på kirkegården eller Graverkontoret, Mejlbyvej 682. Telefon 22888876.