Chrám je postavený na malom vŕšku nad obcou po pravej strane cesty, smerom na Plaveč. Nie sú žiadne písomné záznamy o prvom chráme, ale vieme, že v Orlove farnosť existovala od roku 1366. Z rozprávania medzi ľuďmi je známe, že prvý kostolík bol len malá drevená kaplnka bez veže pokrytá šindľom a s malou vežičkou vpredu. 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 chrámu 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. Chrám bol posvätený 22. júna 1866 a bol zasvätený Svätej prepodobnej Paraskeve, ako patrónke chrámu. Pri tejto obnove bol do chrámu 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 chrám bol opravovaný v roku 1891 za pomoci kresťanov. Farárom bol vtedy Jozef Iľkovič a chrám bol znova posvätený Michalom Andrejkovičom - arcidiakonom. V rokoch 1969 - 1972 bol chrám 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 chráme 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 chrámu bola urobená v roku 2003. V roku 2007 bola na chóre urobená dlažba a nové dvere. V decembri bola v chráme vymaľovaná svätyňa. V roku 2011 boli na chóre urobené nové lavice. V marci 2012 bola kompletne vymenená strecha na lodi 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 chrámu bola urobená v roku 2003. V roku 2007 bola na chóre urobená dlažba a nové dvere. V decembri bola v chráme 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. V lete a v jeseni 2014 boli urobené vonkajšie práce a to, odvodnenie a nový chodník okolo chrámu, prerobené pristupové schody, spevnený svah pod cintorínom a obnovený náter fasády chrámu. V jeseni 2015 bol prerobený múrik vedľa schodov a zhotovené nové nerezové zábradlie. 6.1.2016 bola daná do užívania nádoba na svätenú vodu, ktorá bude veriacim stále k dispozícii. V máji 2016 bol zreštaurovaný celý ikonostas, ktorý urobil Miroslav Mindek. V októbri 2016 pri kaplnke Nepoškvrneného Srdca Panny Márie bolo zhotovené nerezové zábradlie. V máji 2018 bolo urobené nové oplotevie fary. V tom čase bol urobený nový misijný kríž.

V máji 2016 boli začaté práce na oprave kaplnky sv. Cyrila a Metoda. Ukončené boli 1. júla 2017.

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 školy, bola kaplnka Zvestovania Presvätej Bohorodičke, v ktorej sa slúžili bohoslužby od roku 1995 do 12.11.2011. 12. apríla 2008 sa začalo s výstavbou nového chrámu. V máji 2009 bola budova chrámu zmontovaná z prefabrikátov privezených z Prahy. Stavba chrámu bola dokončená 11.11.2011. Posviacka nového chrámu bola 13.11.2011 o 10.00 h. Slávnostnú liturgiu celebroval arcibiskup a metropolita ThDr. Ján Babjak SJ, PhD. Chrám 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.

"O mire vseho mira i blahostojaniji svjatych Božích cerkvej i sojedineniji vsich, Hospodu pomolimsja!"

"Za mier celého sveta, za blaho a rozkvet svätých cirkví Božích a zjednotenie všetkých, k Pánovi pomodlíme sa!"