Kostol - cerkov je postavený na malom vŕšku nad obcou po pravej strane cesty, ktorá vedie smerom na Plaveč. Nie sú žiadne písomné záznamy o prvom kostole, ale vieme, že v Orlove farnosť existovala od roku 1366. Z rozprávania medzi ľuďmi je známe, že prvý kostol bol len malá drevená kaplnka bez veže pokrytá šindľom a s malou vežičkou na priečeli. V roku 1864 sa začala prístavba murovanej veže a sanktária - svjatilišča. Tú prístavbu bolo dobre vidieť, keď sa v roku 1970 dávala nová vonkajšia omietka a stará bola obitá až do kameňa. Patrónom tohto kostola bol v tom čase barón Gejza Salamon. V roku 1866 bola prístavba dokončená, o čom svedčí aj nápis na chráme. Kostol bol posvätený 22. júna 1866 a bol zasvätený Svätej mučenice Paraskeve, ako patrónke chrámu. Pri tejto obnove bol do kostola daný aj nový oltár a ikony. Je na škodu, že nevieme meno umelca ktorý kreslil obrazy na týchto ikonách, pretože maľby ako Kristus či Mária vyzerajú ako živé. Odborný reštaurátor František Šubert povedal, keď bol obnovovať tieto obrazy v roku 1971, že to musel byť veľkolepý odborník a umelec. On sa domnieva, že ten maliar bol pravdepodobne mních z Ľvova a jeho meno bolo utajené kvôli jeho skromnosti. Väčšina obrazov a ikon bola dovážaná do chrámov Božích gréckokatolíckeho obradu práve z Ľvovskej oblasti. Na jednej z ikon môžeme čítať, že kostol bol opravovaný v roku 1891 za pomoci kresťanov. Farárom bol vtedy Jozef Iľkovič a kostol bol znova posvätený Michalom Andrejkovičom - arcidiakonom. V rokoch 1969 - 1972 bol kostol obnovovaný. Zvonka bola urobená nová omietka, natretá strecha a pristavená sakristia. Vnútri bola urobená maľba celého interiéru. Ikony a oltár boli obnovené. Sedem obrazov bolo namaľovaných (vo "freska seco" štýle) do čerstvej omietky odborným maliarom Mikulášom Jordanom a jeho synom akademickým maliarom i ornamentárom Štefanom Fottom. V roku 1970 bola pri kostole vystavaná kaplnka so sochou Nepoškvrneného Srdca Panny Márie a v roku 1977 dobudovaná travertínová stena. V roku 1994 bola natretá strecha, na vežu bola daná medená krytina a nainštalované nové lavice. Plynofikácia kostola bola urobená v roku 2003. V roku 2007 bola na chóre urobená dlažba a nové dvere. V decembri bola v kostole vymaľovaná svätyňa. V roku 2011 boli na chóre urobené nové lavice. V marci 2012 bola kompletne vymenená strecha na lodi chrámu. Začiatkom decembra 2012 bolo stavebne úpravené priečelie chóru a rozšírené schodište. Vo februári až apríli 2013 bol celý chrám vymaľovaný bratmi Miroslavom a Petrom Mindekovcami, vymenené okná a vymenená podlaha v celom chráme. V apríli 2014 boli vymenené lavice.
Hoci je kostol malý, ale živá viera a láska k tomuto chrámu Božiemu nášho veriaceho ľudu je veľká. Tento chrám Boží je pekne udržiavaný v čistote, ako aj jeho okolie, ktoré tvoria lipy, tuje, ruže a iné kvetiny.
Farnosť má pod horou Magura kaplnku zasvätenú slovanským apoštolom Cyrilovi a Metodovi. Od roku 1925 kedy bola vysvätená, konajú sa tam každoročne na ich sviatok 5. júla bohoslužby. Neďaleko kaplnky, asi 200 m, je menšia kaplnka z 19. storočia s prameňom vody. Nad týmto prameňom je oltárik s obrazom Presvätej Bohorodičky. Táto voda je posväcovaná raz za rok, keď sa konajú odpustové bohoslužby.
Vo filiálke Andrejovka, v budove byvalej školy, bola kaplnka Zvestovania Presvätej Bohorodičke, v ktorej sa slúžili bohoslužby od roku 1995 do 12.11.2011. S výstavbou nového kostola sa začalo 12. apríla 2008. V máji 2009 bola budova kostola zmontovaná z prefabrikátov privezených z Prahy. Stavba bola dokončená 11.11.2011. Posviacka nového kostola bola 13.11.2011 o 10.00 h. Slávnostnú liturgiu celebroval arcibiskup a metropolita ThDr. Ján Babjak SJ, PhD. Kostol bol zasvätený Svätému hieromučeníkový Jozafátovi, Polockému arcibiskupovi.
Farská budova v minulosti bola drevená a v druhej polovici 19. storočia vyhorela. Na jej mieste bola narýchlo postavená na kamenných základoch bez nejakej izolácie kamenná budova. Počas druhej svetovej vojny, po vyhodení do vzduchu blízkeho cestného mosta, bola značne poškodená. V auguste roku 2007 boli začaté práce na výstavbe novej farskej budovy. Tá bola za pomoci občanov, sponzorov a závodov v obci dokončená v máji roku 2009. Nová fara bola dňa 31. mája posvätená a daná do užívania arcibiskupom a metropolitom Jánom Babjakom. V auguste 2010 bola stará fara ako nepotrebná budova zbúraná.
1. apríla 2012 bol dekanát v Starej Ľubovni rozdelený a na šarišskej časti okresu bol vytvorený dekanát so sídlom v Orlove.