Kostel svaté Maří Magdaleny je považován za nejstarší stavbu v dnešní vesnici Malý Bor. Nachází se na výrazné vyvýšenině nad obcí, s přilehlou plochou bývalého hřbitova a navazujícím současným hřbitovem. Jeho historie je úzce spjata s historií samotného Malého Boru, která se poprvé objevuje v písemných dokumentech jako osada jménem Bor v listině krále Václava I. z roku 1243.

Stavbu iniciovali páni z Boru, konkrétně Bohuslav a Dluhomil z Boru. Původní části kostela – loď a věž – jsou datovány do první poloviny 13. století, přesněji do let 1230–1240, ačkoli některé prameny uvádějí ještě starší původ z let 1200–1220. Písemně je kostel poprvé doložen v roce 1352, kdy je v dokumentech označen jako farní. Jde tedy o stavbu, která svojí skutečnou historií značně předčí své písemné doložení.

Stavba má charakter jednolodní budovy s podlouhlou lodí, hranolovitou věží, dvěma gotickými kaplemi umístěnými na stranách lodi a presbytářem ze 16. století. Loď je klenuta dvěma poli křížové klenby bez žeber, přičemž jednotlivá pole jsou oddělena širokými oblouky, kterými se vstupuje do věže a do tribuny. Do podkroví se vstupuje severní stranou přes půlkruhově zaklenutý průchod. Tribuna v prvním patře původně sloužila jako čestné místo, kde seděl při mši vlastník panství. Gotické kaple na severní a jižní straně lodi byly přistavěny později. Barokní období přineslo stavbě předsíň u západní stěny a kruchtu s presbytářem.

Stavba si zachovává cenné románské prvky svědčící o jejím středověkém původu. Lze pozorovat dnes již zazděná okna v podkroví kaplí, zachovalé románské zdivo věže a charakteristická sdružená románská okna na obou stranách vrcholku věže. Jako románský prvek je třeba zmínit místnost v prvním patře, která v přízemí přechází do tribuny pavlačové. Stavební materiál – granitové, neboli žulové zdivo – je dnes překryto několika vrstvami omítek, které jej chrání.

Kostel je stavebně pozoruhodný především svojí atypickou dispozicí, kdy je hranolová věž situována v koutu lodi. Takovéto neobvyklé konstrukční řešení se v českých zemích vyskytuje jen zřídka – dalšími příklady jsou kostely v Újezdci u Blatné a v Čestici. Právě díky těmto charakteristickým rysům je kostel řazen mezi stavby strakonické huti. Dnes stojí oddělen zdí od nového areálu hřbitova s budovou márnice.

Kostel svojí polohou a charakteristickou věží dominuje krajině Malého Boru a zůstává svědectvím středověké stavební tradice regionu i dlouhé historie místní komunity.