Osnova sedanje cerkve je bila postavljena 1666. Čeprav se zdi malo verjetno, da vas, kot je Zalog, pred tem ni imela nikakršnega bogoslužnega objekta, dokazov v tej smeri nimamo. Stavba je imela prvotno precej nižje zidovje s pravokotno, ravno in leseno stropano ladjo ter prezbiterij v duhu zadnjih izdihljajev gotske stavbarske tradicije. Bil je triosminsko sklenjen s pristrešenim talnim zidcem, z ozkimi okenci in obokan. Na zunanjost južne stene ladje so umestili fresko svetega Krištofa, ki je bila dopolnjena 1724. Valvasor 1689 v cerkvi našteva tri oltarje, in sicer svetega Matija, svetih Pavla in Luka ter svetega Rešnjega telesa (sedaj Marije Kraljice z Jezuskom). Kmalu za tem okrog 1700 so celotno stavbo nadzidali, jo na novo obokali, znotraj razčlenili s pilastri in venčnim zidcem ter vanjo postavili sedanja stranska oltarja. Stavba ima tudi novejši kor in zakristijo na južni strani. 1820 so za glavni oltar kupili tistega iz cerkve na Gavšeku. 1858 je vse oltarje prenovil Založan Aleš Janežič, ki je 1869 izdelal tudi okvirje za nov križev pot kranjskega slikarja Anselma Bizjaka. Sedanji glavni oltar so pred prvo svetovno vojno izdelali v Tomanovi kamnoseški delavnici v Ljubljani. V južni steni ladje je preprost baročni portal s spominskima ploščama v obeh svetovnih vojnah padlim domačinom.
Na osi pred vhodom je prizidan zvonik. Ta je bil prvotno v pritličju na tri strani odprt, sedaj pa je zazidan, le na osi stavbe vanj vodi polkrožno zaključen portal iz zelenega kamna. Sorodni okviri krasijo tudi zvonikove line. Njegovo pritličje je oblečeno v rusticirano betonsko oblogo, nad njo ima posnete vogale, pod linami izstopajoč venčni zidec, nad njimi pa urine številčnice ter korenasto z bakrom krito streho. V zvoniku vise trije zvonovi. Posebno znamenit je veliki, ki je bil ulit 1434, verjetno v Benetkah. Med najstarejšimi zvonovi v Sloveniji je izjemen po svoji velikosti, saj tehta kar 1450 kg. V Zalog naj bi prišel iz ljubljanske avguštinske cerkve. Po obodu je gladek, le gornji rob plašča ima okrašen z ornamentiko in dolgim dvovrstičnim napisom v gotski minuskuli ter reliefi sedečega, blagoslavljajočega Odrešenika ter več svetnikov. Pod ta zvon spadajo Zgornji, Srednji in Spodnji Zalog ter Cerkljanska Dobrava. Od 1775 imajo s krajšimi presledki v Zalogu svojega duhovnika.
Sveti Matija praznuje 24. februarja, upodablja pa se ga kot apostola v tuniki, lahko tudi s knjigo, najznačilnejši atribut pa je sekira, s katero je bil obglavljen in zaradi katere so ga za zavetnika izbrali tesarji in mesarji.
