Nazwa wsi wymieniana była w 1499 r. a pierwsza cerkiew istniała już w 1507 r. Obecną cerkiew zbudowano w końcu XVIII w. na miejscu poprzedniej, być może z wykorzystaniem elementów budulca ze starszej cerkwi. Na nadprożu przedsionka namalowana jest data 1778, a na drewnianej tablicy fundacyjnej - 1782, co może być interpretowane jako data poświęcenia cerkwi. Była wielokrotnie remontowana, m.in. w latach 1843, 1893 (remont kapitalny, zmiana gontów na blachę), 1930, 1971 i 2007. Po wysiedleniu w 1947 w Krempnej zostały 4 rodziny i ksiądz unicki, Jan Wysoczański, który odprawiał w cerkwi nabożeństwa także dla Polaków, którzy zasiedlili wieś. Od roku 1962 cerkiew była nieczynna z powodu złego stanu technicznego. W 1969 w Krempnej ustanowiona została samodzielna parafia a w 1971 r. odprawiona została pierwsza msza rz.-kat. W latach 1971-72 przeprowadzono kolejny poważny remont. Do roku 2004 cerkiew służyła jako kościół parafialny pw. św. Maksymilana Kolbego, potem funkcję tę przejął wybudowany obok nowy kościół murowany. W latach 2007 - 2012 został przeprowadzony generalny remont cerkwi, podczas którego wymieniono podwaliny i wszystkie zniszczone elementy drewniane a na dachy powróciły gonty. Podczas tego remontu zawaliła się kopuła nad prezbiterium, ale zaraz została zrekonstruowana. Prace konserwatorskie we wnętrzu wykonała Małgorzata Dawidiuk z Przemyśla.

Orientowana, drewniana, konstrukcji zrębowej. Trójdzielna: prezbiterium, szersza nawa i babiniec na planach kwadratów, przy prezbiterium od pn. zakrystia. Wieża konstrukcji słupowo-ramowej o pochyłych ścianach, z lekko nadwieszoną izbicą. Słupy wieży obejmują babiniec. Wokół wieży zachata. Nad wszystkimi częściami dachy namiotowe kryte gontem. Dach nad wieżą bez załamań, nad prezbiterium z jednym załamaniem a nad nawą z dwoma załamaniami. Nad wszystkimi częściami jednakowe hełmy baniaste z pseudolatarniami i żelaznymi krzyżami. Nad zakrystią dach dwuspadowy. Wewnątrz nad nawą i prezbiterium kopuły namiotowe, w babińcu strop płaski na belkach.

Elementy wnętrza:

• Kompletny i będący tu od początku ikonostas z poł. XVIII w, dokończony lub odnawiany w latach 1835-1836 przez malarza Krasuckiego z Przemyśla
• Nad chórem Deesis ze starego ikonostasu z 1664 r., przypuszczalnie z poprzedniej cerkwi
• Nad oknami ramy z prorokami
• Mensa ołtarza głównego w prezbiterium z XVII w. ze sceną Ofiary Abrahama z przodu i Tablicami Dekalogu z tyłu
• Nastawa ołtarza głównego z XVIII w. z obrazami św. Mikołaja i Matki Bożej z Dzieciątkiem (XIX w.).
• Obraz Bogurodzicy Pokrow z XIX w.
• Świeczniki rzeźbione w drewnie z XIX w.
• Tabernakulum drewniane z malowanymi ikonami z XIX w.
• Polichromia w prezbiterium na sklepieniu i ścianach z XVII w.
• Tablica fundacyjna nad drzwiami w przedsionku (1782 rok), mówiąca o przebudowie wcześniejszej świątyni
• Malowidło św. Pawła Apostoła na prawym węgarze wewnętrznych drzwi z XVII w.
• Feretron - figura Matki Bożej z Dzieciątkiem z XVIII w.
• Zamek kowalski w drzwiach wewnętrznych z datą 1783 r.
• Kamienna figura św. Mikołaja przed cerkwią

Kilka starszych ikon z Krempnej znajduje się w Muzeum Historycznym w Sanoku.

Wg klasyfikacji R. Brykowskiegi jest to cerkiew łemkowska, typ północno-zachodni, wariant starszy,