Wieś Czyrną, położoną nad potokiem Czyrnianka wpadającym do Białej, w 1569 roku lokował na prawie wołoskim król Zygmunt August. Od początku była tu parafia, najpierw prawosławna, potem greckokatolicka. Cerkiew, w miejscu poprzedniej, budowano w latach 1893–1894 według projektu Delavo, architekta francuskiego pochodzenia, o czym informuje tablica we wnętrzu świątyni. Przebudowano ją w 1933 roku, a w latach 1979–1983 odnowiono i przywrócono pierwotny wygląd.

To skromna, drewniana świątynia konstrukcji zrębowej, oszalowana pionowymi deskami, zbudowana na planie krzyża z ramionami bocznymi zamkniętymi prostokątnie, zwieńczonymi półkolistymi szczytami. Jest trójdzielna i składa się z zamkniętego trójbocznie, wydłużonego prezbiterium z zakrystią, szerokiej nawy podobnej do transeptu i prostokątnego babińca. Dachy dwuspadowe i jednokalenicowe kryte blachą, wieńczą wieżyczki z cebulastymi hełmami, pozornymi latarniami i żelaznymi krzyżami. Nad nawą znajduje się spłaszczona kopuła z pseudolatarnią i cebulastym hełmem.  Izbicowa wieża słupowo-ramowa o pochyłych ścianach, oszalowana, zwieńczona gzymsem zegarowym i baniastym hełmem z latarnią, wznosi się nad kruchtą, a nie jak w klasycznych cerkwiach nad babińcem. W ścianach nawy widać duże, potrójne okna, a nad nimi ozdobne, zadaszone półkola z okrągłymi okienkami.

Nawę kryje pozorne sklepienie kolebkowe. W prezbiterium znajduje się ikonostas z 1933 roku, a za nim ołtarzyk z XVII wieku z obrazem Matki Bożej z Dzieciątkiem. Rokokowa ikona świętej Paraskiewy z drugiej połowy XVII lub XVIII wieku, niedawno odnaleziona w złym stanie na strychu plebani i poddana konserwacji, mogła być darem wotywnym konfederatów barskich. Cenne są obrazy: Złożenie do Grobu z XVII wieku w barokowym ołtarzu, w zakrystii najstarsza, owalna ikona Ostatnia Wieczerza z XVII wieku, oraz Opieka Bogurodzicy z XVIII wieku z koroną na ramie, jedną z dwóch jakie trzymano nad głowami nowożeńców w dniu ślubu.

Koło świątyni stoi kamienna dzwonnica parawanowa z przełomu XIX i XX wieku w formie potrójnej arkady do zawieszenia dzwonów. Jest też plebania i spichlerz z XIX wieku oraz cmentarz z kilkoma kamiennymi nagrobkami. We wsi zachowały się zabudowania połemkowskie, krzyże przydrożne i kapliczki oraz tradycyjne, zrębowe spichlerze zwane sypańcami, sklepione kolebką, pokryte warstwą ziemi i zadaszone.

Obecnie rzymskokatolicki kościół jest pod wezwaniem Niepokalanego Serca Najświętszej Maryi Panny.

Świątynia znajduje się na Szlaku Architektury Drewnianej w Małopolsce.

Przy dawnej cerkwi św. Paraskewy Męczennicy w Czyrnej stoi dzwonnica. Wolnostojąca budowla pochodzi z przełomu XIX i XX. Dzwonnica jest parawanowa, murowana z kamienia w której wiszą trzy dzwony. Najstarszy dzwon pochodzi z I połowy XX wieku z roku 1921 a dwa następne wykonano w 1981 roku.