Kostel sv. Mikuláše stojí v Proseči od nepaměti. V dnešní podobě je od roku 1913. Nejkrásnější a nejstarší část starého raně gotického kostela se vzácnou jednoducho žebrovitou klenbou - presbyteriem, byla však jako nejcennější stavba v Proseči a okolí zachována.
Vznik kostela v osadě Proseč při rychtě prosečské spadá buď do konce 13. století, nebo do začátku století 14.(Bývá uváděno i dřívější období kolem r. 1235.) Způsob jeho stavby (viz presbytář, levou kapli) ukazuje na dobu lucemburskou. Je možné, že původně bylo presbyterium jen kaplí a teprve později byla přistavěna kostelní lod´. Jisté však je, že celý kostel i s lodí (tak, jak asi vypadal starý kostel ještě před zbořením roku 1912) stál již v roce 1350.
První historicky datovaná zmínka o chrámu Páně sv. Mikuláše v Proseči, a to jako o kostele farním, je tedy z roku 1350. Toho roku za vlády Karla IV. První pražský arcibiskup Arnošt z Pardubic dal zhotovit seznam kostelů v Čechách a zde v nově vzniklém biskupství litomyšlském a děkanátu mýtském je jmenována vedle osady "Božího dobu" (Nové Hrady) také Proseč. Byl tedy prosečský kostel do husitských bouří kostelem farním.
Přestože Prosečí táhla husitská vojska, prosečský kostel nebyl vypálen, patrně jen vydrancován a poničen. Se starou prosečskou farou byly zničeny i všechny dokumenty, takže přesné zprávy z dob předhusitských, kromě originálu soupisu v klášteře rajhradském z r. 1350 nemáme.
Po husitských bouřích v době nekatolické patřila Proseč patrně pod duchovní správu v Luži. Roku 1600 bylo novohradské panství již v držení Anny z Lobkovic, provdané za Pavla hraběte z Trautsohnů-katolíků. Od té doby zde působili katoličtí kněží. Ovšem kostel v Proseči byl, patrně pro nedostatek kněží, jen kostelem filiálním, připojeným k novohradskému kostelu sv. Jakuba.
V roce 1610 věnoval hrabě z Trautsohnů s chotí prosečskému kostelu velký zvon "sv. Mikuláš". Velká oprava byla provedena v roce 1625. Svědčila o tom různá malta, která spojovala ramenné zdivo u presbytáře a severního traktu starého kostela. Kostel byl toho roku přestavěn a rozšířen. Presbytář zůstal původní.
Roku 1754 se stal prosečský kostel po 333 letech opět farním.
Starý kostel prostorově již nedostatečný se stal pro porušenou statiku neopravitelný. Proto byl, krom zvonice, která stála samostatně, a již uváděného presbytáře ( původního prostoru kolem hlavního oltáře starého kostela roku ), roku 1912 během dvou dnů zbořen a za jeden rok postaven kostel nový, rozsáhlejší, s hlavním oltářem na jižní stranu. Kostel je spojen se zvýšenou věží, dnes 34 m vysokou, kterou prochází hlavní vchod. Nový kostel byl vysvěcen 6.července roku 1913.
Prosečský kostel má zachovány památky na nejstarší církevní stavbu v okolí. Škoda, že při husitských bouřích byly zničeny všechny staré církevní dokumenty a stáří původního kostela můžeme jen odhadovat.