Dawna cerkiew greckokatolicka z XVIII w. pw. śś. Kosmy i Damiana, orientowana, trójdzielna, zbudowana w miejscu poprzedniej (lub przebudowana), która stała 275 lat. Mówi o tym tablica fundacyjna z 1782 r. znajdująca się nad wewnętrznym portalem. Dachy posiada namiotowe, wysokie, dwukrotnie łamane, kryte blachą, zwieńczone baniastymi hełmami i krzyżami.
Parafia greckokatolicka przestała istnieć, gdy w 1947 r. wysiedlono z Krempnej większość Łemków. Na miejscu pozostał jej były proboszcz ks. Jan Wysoczański, który odprawiał nabożeństwa w obrządku łacińskim dla nowych, rzymskokatolickich mieszkańców. Po 1956 r. część Łemków powróciła, ksiądz wrócił do obrządku unickiego, zaś dla Polaków utworzono w Krempnej filię rzymskokatolickiej parafii z Desznicy. W 1969 r. erygowano w Krempnej parafię rzymskokatolicką pw. św. Maksymiliana Kolbe, jednak zezwolenie na użytkowanie świątyni uzyskano dopiero w 1971 r. (po 9-letnim zakazie przez władze powiatowe). Funkcję kościoła parafialnego pełniła do 2004 r. do czasu wybudowania nowego – murowanego.
Cerkiew umiejscowiona jest w centralnej części wsi, w pobliżu drogi do Polan.
Wewnątrz znajduje się kompletny, XVIII wieczny ikonostas dokończony lub odnawiany ok. 1835 przez Krasuckiego, malarza pochodzącego z Przemyśla oraz rokokowy ołtarz główny z obrazem św. Mikołaja i drewniane tabernakulum z ikonami na ściankach. Nad chórem najcenniejszy zabytek świątyni — rząd deesis pochodzący ze starszego, XVII-wiecznego ikonostasu: ikona Chrystusa Pantokratora z Matką Bożą i św. Janem Chrzcicielem, a po bokach przedstawienia dwunastu apostołów. W zachodniej części cerkwi dekoracyjny chór śpiewaczy w formie galerii obiegającej babiniec i zachodnią ścianę nawy. Ściany sanktuarium pokrywa klasycystyczna polichromia z końca XVIII w. o motywach architektonicznych z ornamentyką arabeskowo-kandelabrową. W przedsionku XVIII-wieczny feretron Matki Bożej i malowidło św. Pawła na węgarze portalu. Przed cerkwią stoi kamienna figura św. Mikołaja, pochodząca z XIX w., wykonana w ośrodku kamieniarskim w Bartnem. Zachowane dwa cerkiewne dzwony znajdują się na dzwonnicy obok nowego kościoła.
W latach 2007-2013 r. został przeprowadzony gruntowny remont świątyni oraz konserwacja całego wyposażenia, dzięki któremu odzyskała swój dawny blask.