Kostel svatého Martina vyrostl v srdci obce Mlékojedy na obdélné návsi, na vyvýšené terase bývalého hřbitova. Ten obklopuje litinový plot s gotisujícími tvary z roku 1885. Je chráněn jako kulturní památka od roku 1964.

Stavba má gotické kořeny z čtrnáctého století. Poprvé se připomíná jako farní kostel v roce 1384. Jako mnohé české sakrální stavby byl během husitských válek poškozen, přesto zůstal roku 1465 katolický. Roku 1592 jej postihl požár, po kterém věž byla obnovena a dostala poslední patro se sgrafitovanou omítkou. Nejzávažnější změnu přinesla rok 1776, když došlo k radikální přestavbě na pozdně barokní podobu – stavba byla zbourána až na věž, nový objekt si však zadržel stejné rozměry. Následující století přinesly povodně (1845, 1890, 2002). Po roce 1945 budova postupně chátřela, od druhé dekády dvacátého prvního století se však postupně rekonstruuje.

Architektonicky se jedná o jednolodní stavbu s polokruhově uzavřeným presbytářem z roku 1776 a malou sakristií na severní straně. Dominantní prvek – mohutná hranolová věž v západním průčelí – pochází z gotické doby. Po požáru roku 1592 byla obnovena a uchovává si renesanční sgrafitové kvádrování. Dolní patra věže se otevírají pravoúhlým portálem a štěrbinkovými okénky, horní zvonové patro má čtyři velká zvuková okna. Jehlancová střecha věže je završena korouhvičkou s letopočtem 1595. V lodi se nacházejí pilastrové svazky s rokajovými hlavicemi a plackové klenby; velká pozdně barokní okna se vyskytují především na jižní straně.

Vnitřní vybavení nese jasné znaky rokoka. Hlavní oltář z roku 1776, zhotovený z umělého mramoru od M. Hennevogela, má bohatě řezaný a zlacený barokní rám z počátku osmnáctého století. Postranní oltář Pohřbívání Krista je pozdně renesanční, dřevěný, se čtyřmi sochami a původním deskovým obrázkem téhož motivu z doby kolem roku 1600. Součástí vybavení jsou také kazatelna, obraz sv. Jana Křtitele, socha Jezulátka a varhany – všechny díla rokokových tvarů z konce osmnáctého století. Rekonstrukční práce přesunuly toto zařízení do depozitáře.

Okolí kostela украšuje několik dalších sakrálních prvků. Na pilíři u čp. 77 se zachovává barokní soška sv. Floriána z roku 1707. Na západním konci obce stojí železný barokní kříž z doby kolem roku 1680 s bohatě tepanou mřížovinou; roku 1839 jej přenesli ze zrušeného kostela sv. Michala v Litoměřicích. Na východní straně obce se pak nachází jednoduchý křížek na podstavci.