Nejdecká história tohoto chrámu se zahájila v rozmezí let 1341 až 1354, kdy zde nechal gotický kostel postavit Petr Plik. Datace vychází z analýzy historických záznamů: lenní list Jana Lucemburského z roku 1341 velmi podrobně vyjmenovává Plikův majetek včetně hradu Neudek, avšak kostela nezmíňuje. Naopak Erekční knihy pražské arcidiecéze z 24. července 1354 zaznamenávají zřízení faráře, což předpokládá existenci farnosti. Z toho lze usuzovat, že kostel vznikl právě v těchto třinácti letech.

Rod Šliků, který vlastnil nejdecké panství v rozmezí let 1446 až 1602, chrám postupně přestavěl a zvětšil. Roku 1513 se uskutečnila obnova interiéru a na strop byl zapsán letopočet. Od roku 1562 do 1624 vedly církevní záznamy evangelické pastory, svědčící o dopadech reformace. Vypuzení evangelického faráře Valentýna Löwa roku 1624 zanechalo kostel bez řádného vedení na dva roky. Křty a farní záležitosti pak vykonávali střídavě učitel, porodní bába, děkan z Lokte a farář z Chodova. Řád se obnovil, když loketský děkan dosadil nejprve faráře Leonarda Löfflera a 9. listopadu 1627 faráře Jiřího Brauna.

Saský vpád roku 1631 přinutil faráře Brauna k útěku. Vrátil se však 11. srpna 1632, poté co císařské pluky Sasy znovu vytlačily. Krátce nato zemřel, pravděpodobně na mor, který v Nejdku tehdy řádil.

Od roku 1641 do 1661 zde působil páter Jiří Lanka, cisterciák z pláského kláštera. Zprvu se zdržoval jen občas, od roku 1648 se usadil trvale. Na jeho iniciativu byla zakoupena budova nad kostelem se zahradou, kde byla zřízena farní škola. Roku 1656 byl pro chrám pořízen velký zvon od manželky hraběte Humprechta Černína.

Farář Jan Jakub Langer (1708–1733) přinesl nový impuls. Roku 1709 založil škapulířové bratrstvo a v roce 1711 provedl rozsáhlou obnovu chrámu – byl nově zastřešen. Roku 1726 byla postavena nová fara, která do té doby hrozila zřícením. K nejdecké faře patřily čtyři kaple: Křížová kaple na starém hřbitově, nemocniční kaple, zámecká kaple a kaplička na Boží louce.

Nejzásadnější stavební proměna proběhla v letech 1755 až 1756. Kostel byl zvětšen o více než polovinu své původní velikosti, změnily se jeho orientace a půdorys. Původní směr hlavního oltáře od východu se posunul na severovýchod. V této podobě se kostel dochoval až do dnešních dnů.

Architektonicky jde o jednolodní zděný barokní kostel obdélného půdorysu se kruhově uzavřeným presbytářem a sakristií. Lod člení pilastry s kompozitní hlavicí, které nesou zalamovanou římsu – typický prvek rustikální barokní architektury. Původně se při kostele nacházel hřbitov, který byl přemístěn před rokem 1600. Kostní pozůstatky nalezené při práci na vodovodu roku 1909 svědčí o jeho dřívější existenci.

Dnes se chrám obklopují historické pamětní předměty. Nejstarší jsou socha svatého Jana Nepomuckého z roku 1710 a barokní sloup se sochou Nejsvětější Trojice z roku 1717, obě rovněž chráněny jako kulturní památky od roku 1964 spolu s kostelem samotným. Roku 2005 byl přidán dvanáctimetrový mariánský sloup z pískovce od akademického sochaře Michala Moravce, který nahradil starší sloup se sochou Panny Marie.

Kostel svatého Martina v Nejdku je tak živým dokladem složitých a vrstevnatých dějin tohoto horského kraje – od gotických počátků přes bouřlivou reformaci a rekonverzaci až k harmonickému baroku osmnáctého století.