Kostel ve Staré Kdyni je zmíněn poprvé koncem 14. století. Jedná se o gotický kostel s typickými křížovými klenbami presbyteria, gotickými okny a hranolovou věží z doby pozdně gotické přestavby. Roku 1734 byla věž upravována, došlo k jejímu zvýšení a přibyla barokní cibulovitá báň. Jako architekt je uváděn V. Fischer z bavorského Furth im Wald. V 60. letech 18. století pokračovala přestavba kostela financovaná majiteli panství, hrabaty ze Stadionu. Jejich erb je v průčelí kostela. Při přestavbě vznikly boční kaple, loď byla prodloužena. Na rokokovém oltáři je obraz sv. Mikuláše od Ignáce Raaba. Stará Kdyně měla původně kostely dva, kromě Mikuláše zde stával možná ještě starší kostel sv. Petra, který zanikl v 17. století.
Po vzniku Nové Kdyně místním začalo vadit, že nemají kostel na náměstí, opakovaně se uvažovalo o stavbě nového kostela, ke které však nikdy nedošlo. Kostel se dočkal opravy v 90. letech 20. století a počátkem 21. století. Poblíž kostela ve Farní ulici stojí fara s vjezdovou branou.
