Kostel sv.Matěje v Horšicích je  gotický, první písemná zmínka z roku 1352, loď a presbytář z doby kolem poloviny 14. století. Barokní úpravy kostela se uskutečnily v 1. polovině 18. století (krovy, strop lodi), na konci 18. století byla postavena kaple sv. Kříže s hrobkou; v roce 1859 byla přistavena věž.

Osada Heršice se uvádí v roce 1245. Kostel sv.Matěje je poprvé písemně doložen roku 1352. Podle dochovaných architektonických prvků lze loď s jižním portálem a presbytář s klenbou do období kolem poloviny 14. století; soudobá se zdivem jsou také všechna okna lodi a presbytáře, opěráky, vítězný oblouk a zřejmě i sedile, sanktuář a štít nad vítězným obloukem.


Při stavbě bylo do stěn zazděno několik kusů klenebních žeber, které se shodují s profilem žeber klenby presbytáře. Mohlo jít o nadbytečné nebo nepodařené kusy. Další úpravy lze zřejmě spojit s 1. polovinou 18. století, kam bychom mohli zařadit krov lodi a presbytáře (nelze vyloučit časový odstup mezi oběma konstrukcemi). Společně provedený nejspíše i strop lodi a korunní římsy. Situace v západním poli krovu naznačuje, že střecha na západní straně končila malbou. Na sklonku 18. století byla dle údajů v literatuře postavena kaple sv. Kříže s hrobkou. (nákladem Václava Henigára z Eberku); z doby její výstavby portál, okna i klenba se zastřešením; do presbytáře prolomený z kaple vstup.


Snad v klasicismu byla postavena sakristie a s tím prolomený vchod ve zdi presbytáře; výklenek v JV zdi presbytáře může být z této doby. V roce 1859 byla přistavěna věž, která nahradila samostatně stojící zvonici. Pravděpodobně všechny konstrukce a otvory ve věži patří době výstavby (včetně krovu a zvonové stolice). Spolu s věží byla postavena i kruchta a západní štít lodi. Předpokládanou západní valbu střechy lodi nahradilo sedlo. Sakristie byla v 1. polovině 20. století asi znovu vystavěna. Tehdy asi odstraněny opěráky ze západních nároží lodi. V letech 1962 – 1965 byla provedena celková oprava. V roce 2001 byla sakristie zbourána a související vstup do presbytáře zazděn. Jižní úsek ohradní zdi s navazujícími částmi na V a Z může být ještě barokní; ostatní části ohrazení se vstupními bránami jsou asi z 19. století. Do konce 19. století asi také náleží márnice. V ohradní zdi hřbitova je v nice umístěna pozdně barokní socha sv. Jana Nepomuckého.