Orientovaný jednolodní kostel o lodi obdélného půdorysu, na niž navazuje půdorysně menší čtvercové presbyterium, je vyzděn z lomového a kvádrového kamene.Tesané kvádry tvoří nosné žebrové pruty klenby v presbytáři, vítězný oblouk, pastoforium a ostění odkrytých, původních oken tamtéž. Cihelné zdivo je použito v záklencích renesančních, barokních a empírových oken. Hladké omítky jsou provedeny v monochromii. Z jihu je k rozhraní lodi a sakristie přistavěna přízemní, půdorysně obdélná sakristie, v hloubce navazující na sousední jižní kapli. Západní průčelí presbytáře obsahuje jeden lomený okenní otvor v nálevkovité špaletě. Ve východní zdi jižní sakristie jsou proraženy dva obdélné okenní otvory, v jižní zdi jsou dveře. Fasáda jižní sakristie je členěna lizénami, jejichž jihovýchodní nároží a levý okraj obíhá plochá horizontální nadpraží lišta. Korunní římsa pod valbovou střechou je stupňovitě profilována. Jižní přístavba s kamenným armováním nároží má přibližně kosodélníkový půdorys a oproti kostelu kratší délku. V jednoosém jižním průčelí jižní kaple je pískovcový pravoúhlý portál, jehož horní, segmentem završený překlad s okosenou dolní hranou nese dataci MD XXIX, sestavenou okolo znaku zednické lžíce a kladívka. V nesymetricky zasazené svislé ose je nad vchodem prolomen půlkruhový okenní otvor s šestitabulkovou výplní. Půdní bedněné patro zvonice je opatřeno podsebitím. Valbová střecha se přimyká k sedlové nad lodí a ve východní části hřebene nese dřevěný sanktusník kruhového půdorysu s kuželovou stříškou. Západní zeď jižní kaple je hladce omítnuta stejně jako západní zeď lodi, kterou zvnějšku diagonálně podepírají dva mohutné dvoustupňové pilíře s pultovými stříškami. Ve středové ose je vstup do lodi rámovaný pravoúhlým pískovcovým portálem a půlkruhové okno. Severní průčelí lodi je dvouosé, okenní otvory mají půlkruhové záklenky, fasáda je hladká. K rozhraní severního průčelí lodi a presbyteria je přistavěna přízemní sakristie s valbovou střechou. Ve všech jejích zdech jsou asymetricky proraženy obdélné okenní otvory, z nichž severní je zaslepený. Presbyterium zvenku podepírají dva dvoustupňové opěrné pilíře. Ve středové ose východního průčelí presbyteria je štíhlé gotické okno s lomeným záklenkem a v hluboké nálevkovité špaletě. Z historie památky Kostel, přesněji řečeno jeho současný gotický presbytář z poloviny 13. století, byl původně kaplí Všech svatých u dvora ve Vyšehorkách, který náležel k líšnické tvrzi. Dle dosavadních znalostí byly kostely s kvadratickou apsidou stavěny ve druhé polovině 13. stol., většinou v nově kolonizovaných oblastech. Roku 1546 prodal Václav Haugvic vsi Vyšehoří (Vyšehorky, něm. Allerheiligen), Podolíčko a Podolí, pustou ves Úvoz a újezdský dvůr Vratislavu Lhotskému ze Ptení, ale již roku 1551 koupil tento majetek od Lhotského olomoucký biskup Jan Doubrava, který jej téhož roku přenechal v léno svému mírovskému hejtmanovi Jindřichu Kobylkovi z Kobylí. Ten získal Vyšehorky a v kostele zřídil rodinnou hrobku. Tak se v kostele dochoval náhrobek samotného Jindřicha Kobylky z roku 1576, dcery Václava Kobylky Aničky z roku 1581 a manželky Jindřicha Kobylky Anny z roku 1560. Souvisí s tím dochovaný úzký okenní otvor se segmentovým záklenkem ve východní stěně, vyzděný z cihel v kamenném zdivu. V jižní kapli je doložen oltář sv. Vendelína staršího původu. Roku 1768 byl kostel opraven, v presbytáři přitom byly zakryty pod několika vrstvami původní freskové malby, znázorňující nejstarší podobu erbů líšnické větve Kunštátských. Na hřbitově se pohřbívalo až do r. 1879. V roce 1957 kostel zcela vyhořel. Shořely nejen původní střecha kostela i věže, krytá ještě šindelem, ale i dřevěný strop, zvon (původní zvon z roku 1511), bylo poničeno zdivo a zdevastováno vnitřní zařízení. Po požáru kostel zůstal několik let úplně bez zastřešení, nejnutnější opravy proběhly až v letech 1963-1964. Zvonové patro a střecha byly nově vybudovány po požáru v roce 1957. Dřevěné jednoramenné schodiště vně západního průčelí, vedoucí do kruchty se nedochovalo a ani nebylo obnoveno. V roce 1994 proběhl v rámci celkové rekonstrukce archeologický průzkum.