Den lille kirke er bygget af rå marksten. Hjørnerne er dog tildannede kvadre. Koret og skibet er romansk, mens tårnet er en sengotisk tilbygning.

Kirkens våbenhus er først opført i 1800-tallet.
Den oprindelige sydportal benyttes stadig, mens nordportalen er tilmuret og kun svagt kan anes. Et tilmuret romansk vindue kan ses i korets øst gavl. Overliggeren er ret ujævnt hugget og hører ikke til den romanske kunsts prægtigste eksemplarer.

Til gengæld rummer kirkens indre nogle smukke kalkmalerier. De dækker halvdelen af skibets nordvæg samt hele korbuen. I korbuen ser man i nord Jomfru Maria i solgissel (Maria i stråleglans) og i syd Anna Selvtredje (Marias moder Anna med både jomfru Maria som barn og Jesus-barnet). Billederne er malet ved 1500-tallets begyndelse, og de var meget yndede i middelalderens slutning. Det øverste stykke af buen er bemalet med blad- og rankedekorationer.

Billederne på skibets nordvæg er en serie malerier fra lidelseshistorien. De er malet en smule senere – i midten af 1500-tallet – af en kunstner, som også har lavet arbejder andre steder på Salling.

Bortset fra granitdøbefonten, som er romansk med en glat kumme, er inventaret af noget nyere dato. Kirkens altertavle er malet af Viborg-maleren A.F. Jæger i 1866 og er en afbildning af den velsignende Kristus. Prædikestolen er fra omtrent samme tid. Den har snoede hjørnesøjler, men er ellers ganske enkel.

Under den grundtvigske vækkelse i sidste halvdel af 1800-tallet var både Lem og Vejby kirker genstand for så stort et røre, at folk strømmede til fra hele Sydvestsalling, så det var mere eller mindre umuligt at komme ind i kirkerne om søndagen.