Kostel sv. Martina leží v jihovýchodní části velemínské návsi, je jednolodní. Na obdélnou loď navazuje užší presbytář se segmentovým zakončením a postranní nízká sakristie na obdélném půdorysu. Při západním průčelí se pak nachází hranolová věž čtvercového půdorysu. Kostel kryje sedlová střecha s polokuželovou částí nad závěrem presbytáře. V úrovni dolní třetiny výšky sedlových střech jsou ve střešních rovinách osazena volská oka. Na podélných stranách jsou pravidelně rozmístěna tři volská oka. Sakristie je zastřešena valbovou střechou. Na rozhraní hřebene střechy a polokuželového zakončení presbytáře nasedá sanktusník. Hranolovou věž kryje stanová střecha se zvonicovým nástavcem, makovicí a křížem. Krytina je tvořena režnou pálenou střešní taškou typu bobrovka v korunové skladbě. Na stanové střeše věže jsou bobrovky kladeny jednoduše. Zbývající část věže a sanktusník jsou pak oplechovány. Plechové pásy jsou spojovány stojatou drážkou. Povrchová úprava plechu je přizpůsobena barevnosti bobrovek. Fasáda je provedena ve okrové barvě s bíle zdůrazněnými architektonickými články (římsy, ostění, pilastry).