Jednolodní stavba s pětibokým závěrem a čtyřbokou věží se nachází v areálu bývalého hřbitova ohrazeného robustní zdí s budovou márnice a božími muky. Kostel sv. Martina je jedinou památkou, která se ve městě dochovala ze středověku. Má vzhled pevnosti obehnané vysokou zdí. Kostel není jednotnou stavbou, ale souhrnem částí staveb pocházejících z různých dob. Nejstarší stavbou je loď a věž, které byly postaveny pravděpodobně ve 13. století na skalním ostrohu. Kostel jako takový byl dostavěn v 15. století a později byl barokně opraven. Kolem roku 1662 měl kostel dokonce 5 oltářů, nynější oltář je postaven podle návrhu ing.arch. Karla Náhunka z roku 1938. Kazatelna je z roku 1785 a pochází od jihlavského sochaře Jana Václava Prchala, jehož dílem je i oltář sv. Kříže v kostelní kapli. Boží muka vedle sakristie byla vysvěcena v roce 1716. V 18. století došlo k vystavění nové kruchty, jižní sakristie a panské oratoře, na jejichž výstavbě se podílel místní zednický mistr Jakub Lysý. Při opravách kostela v roce 1938 byly v gotickém kněžišti pod starou omítkou objeveny nástěnné malby z 15. století. Na věži byly v minulosti tři zvony, které byly v dubnu 1942 sejmuty a odvezeny do Hamburku, odkud se prozatím nevrátily. V roce 1950 byl pořízen nový zvon sv. Josef (665 kg).

V současnosti se kostel skládá z gotického kněžiště s přilehlou kaplí a sakristií, jednoduché lodě a čtyřboké věže. Kostel je 33 metrů dlouhý, devět a půl metrů široký a je k němu přístup po 30 schodech. Zajímavými prvky kostela jsou gotický náhrobek Jana z Hodic či renesanční náhrobek Kryštofa Vencelíka a pozdně gotická kamenná kazatelna.

Za kostelem se do roku 1813, než byl zřízen současný hřbitov, pochovávalo. Kosti ze starých hrobů jsou uloženy v přilehlé kostnici. Jsou zde umístěny i ostatky francouzských vojáků, kteří v době napoleonských válek zemřeli v Třešti na choleru. Okolo kostela jsou umístěny náhrobky významných osobností ze 17. a 18. století. Kostelu sv. Martina náleží také fara, jejíž jádro pochází z roku 1615 a v jejímž výklenku se nalézá rokokové sousoší reliéfního charakteru, a kaplanka, která pochází z roku 1771.