První písemná zmínka o Horšově, který byl od nepaměti v majetku pražského biskupství, pochází z let 1182-1192. Tou dobou byla zdejší osada s tvrzí důležitým správním centrem celé oblasti. Do období poslední třetiny 12. století je také možno klást počátky kostela Všech svatých. Románský kostelík byl však podstatně menší, než je dnešní kostel a byl opatřen tribunou.
V období 60. let 14. století došlo k přestavbě původního kostela v gotickém slohu do podoby, kterou si objekt v zásadě uchoval dodnes. V té době byl Horšov samostatnou farností a biskupský dvorec byl sídlem tzv. nápravníka. Přestavba kostela Všech svatých znamenala podstatné rozšíření lodi severním směrem. Kostel byl dostavěn o presbyterium ukončené pětibokým závěrem s vnějším opěrným systémem a sklenuté dvěma poli křížové klenby.
Klenba a stěny presbyteria byly opatřeny nástěnnými malbami znázorňujícími symboly evangelistů a galerii postav Všech svatých na pozadí bohatého arabeskového dekoru. Jedním z nejcennějších dokladů přestavby kostela v gotickém slohu je unikátní krov nad presbyteriem. Krátce po dokončení přestavby kostela byla k jižní straně presbyteria přistavěna kaple svaté Barbory.
Klenba i vnitřní stěny kaple svaté Barbory byly opatřeny malířskou výzdobou, z níž se do dnešní doby zachovala pouze část na východní stěně. Tato starší malířská výzdoba byla později, dle datace 1489 v nápisové pásce, překryta novou malířskou výzdobou s výjevy z legendy o životě svaté Barbory. Donátorem vnitřní výzdoby kaple byl Dobrohost z Ronšperka, jehož rodový znak je malířsky proveden na svorníku křížové klenby. Gotickou přestavbou byl v tomto období půdorysný vývoj kostela v zásadě ukončen. Jeho novější výraz doplnila ještě na počátku 16. století štíhlá kostelní věž opatřená soudobým zvonem.
Poslední velká slohová přestavba kostela byla uskutečněna v období před rokem 1745. Na výraz exteriéru stavby měla pouze dílčí vliv, zásadnějším způsobem se projevila v jejím vnitřku. Interiér byl opatřen novou dvoupatrovou tribunou a upravena byla i okna v lodi kostela. Plochý strop i stěny v lodi kostela stejně jako vnitřní špalety oken byly opatřeny štukovou výzdobou s povrchovou úpravou v podobě mramorování. Vnitřek kostela byl v tomto období nově zařízen oltáři připisovanými dílně plzeňského sochaře Karla Legáta. Po umělecké stránce velmi hodnotnými a slohově jednotnými prvky. Z tohoto období pochází hlavní oltář Všech svatých, oba boční oltáře svaté Anny a Panny Marie, chórové lavice, kazatelna a chórová mřížka.
V 18. století byl prostor hřbitova při kostele Všech svatých opatřen kamennou ohradní zdí se vstupní bránou. K západnímu průčelí kostela byla přistavěna předsíň. V 90. letech 20. století převzal zcela zchátralý kostel Památkový ústav v Plzni. Dle vyjádření duchovního otce pana Marka Badidy se mše konají vždy pro danou komunitu.
Současný význam a správa
Kostel Všech svatých v Horšově reprezentuje významné sakrální a kulturní dědictví. Průchod historií od románských počátků ke gotickým a barokním úpravám odráží proměny liturgického prostoru i urbanistického rámce vesnice. Zachované malířské výzdoby a architektonické detaily, včetně unikátního krovu nad presbyteriem, svědčí o vysoké úrovni středověkého i raně novověkého stavebního a výtvarného umění v regionu. Kaple svaté Barbory doplňuje komplex o další historicky cenný prvek, který v sobě spojuje náboženské a rodové významy donátora.

| Období | Klíčové změny |
|---|---|
| 12. století | počátky kostela Všech svatých, románský kostelík s tribunou |
| 60. léta 14. století | přestavba na gotický sloh, rozšíření lodi |
| 14.-16. století | klenby, malířská výzdoba, kaple sv. Barbory, věž |
| 1820-1745 | poslední velká slohová přestavba, interiérové změny |
| 20. století | správa Památkového ústavu, opravy pro komunitu |