První písemná zmínka o Horšově, který byl vždy v majetku pražského biskupství, pochází z let 1182–1192. V té době 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. Z románské podstaty kostelíka se dochovala část západní a jižní stěny lodi.


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. Malby byly odkryty v průběhu obnovy vnitřku kostela v roce 2005.


Jedním z nejcennějších dokladů přestavby kostela v gotickém slohu je unikátní krov nad presbyteriem. Konstrukce krovu je podle výsledků dendrochronologického průzkumu datována do roku 1363 a patří mezi nejstarší konstrukce tohoto druhu u gotických církevních staveb v Čechách.


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. Ten je ve věži zachován dodnes.


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. Kostelní lavice a varhanní pozitiv pocházejí až ze druhé třetiny 18. století.


Kostel je jednolodní, obdélný s polygonálně ukončeným presbytářem, obdélnou kaplí sv.Barbory na jižní straně a s hranolovou věží na jihozápadním nároží lodi. Věž má na jižní straně románské okno, v horní části gotická obdélníková okna se středním kamenným křížem.


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íň. Poslední větší stavební úpravou v 19. století byla rekonstrukce věžní báně a provedení nových vnějších omítek fasád kostela.


V 90. letech 20. století převzal zcela zchátralý kostel Památkový ústav v Plzni. V období let 2001–2005 byla za přispění Ministerstva kultury ČR v rámci Programu záchrany architektonického dědictví ČR a Programu restaurování movitých kulturních památek uskutečněna celková památková obnova areálu kostela a jeho hodnotného vnitřního zařízení.