W rektoracie są dwa kościoły, byłe cerkwie. Leluchowska św. Dymitra (Demetriusza) z Solunia (Salonik), otoczona ogrodzeniem z kamieni polnych i lipowym starodrzewem, to obecnie kościół pw. Macierzyństwa NMP, który w 2011 r. obchodził 150-lecie. Być może jednak w owym 1861 r. został tylko rozbudowany lub przeniesiony z innego miejsca i przebudowany, bo wiadomo, że nie była to pierwsza cerkiew grekokatolicka we wsi – przed nią istniały wcześniejsze.
Z 1722 r. pochodzi ikona św. Mikołaja ufundowana przez zamożną rodzinę Krynickich (Krenickich), którzy byli potomkami dziedzicznych sołtysów w Leluchowie, a także w Krynicy, Dubnem i Wojkowej. Konkretnie ufundowali ją Foma (Tomasz) i Maria Kryniccy herbu Korab. Natomiast z dokumentu z 1736 r. wynika, że istniejąca już wtedy w Leluchowie cerkiew została uposażona przez biskupa grekokatolickiego Felicjana Konstantego Szaniawskiego.
Istnieje ustny przekaz, że w latach 1708-9 cerkiew z Leluchowa, podobno dwupoziomową, bo z piwnicą, przeniesiono (sprzedano?) gdzieś na Słowację. Wymienia się rusińską miejscowość Venecia k. Lukova. Z tym, że – jak sprawdzono – tamtejszy kościół datowany jest na 1706 r., co by historycznie nie bardzo pasowało. Ale może sprzedano nie całą cerkiew, lecz jej wyposażenie?
O istnieniu wcześniejszych cerkwi mogą też świadczyć cmentarze łemkowskie, bowiem oprócz szczątków tego tuż obok kościoła, na terenie wsi znajdowały się dwa inne, po których prawie już nie ma śladów. Powyżej sąsiadującego bezpośrednio z kościołem łemkowskiego (o historii jednego z grobów piszemy w części o okresie łemkowskim w przeszłości wsi) zlokalizowano cmentarz katolicki, na którym pochowanych jest ponad 60 osób. Od 1947 r. tak niewiele, gdyż najpierw polscy osadnicy na miejsce wiecznego spoczynku wybierali jeszcze ojczyste strony, z których przybyli do Leluchowa, traktowanego początkowo jako tymczasowy adres zamieszkania. Pierwszy grób pochodzi z 1953 r.
Na wieży (wyryto w niej datę 1860) wisi dzwon Piotr i Paweł, odlany w 1953 r. i zakupiony przez parafię w Muszynie w 1958 r., a na pokrytej blachą miedzianą dzwonnicy dwa inne – św. Dymitr i Maryja wykonane w ludwisarni Felczyńskich w Przemyślu. Na obu figuruje rok 1990 oraz inskrypcja: „Ufundowany przez ks. prałata Franciszka Korta, gdy rektorem był ks. Mieczysław Czekaj”. Ów ks. Korta, któremu leluchowianie zawdzięczają te dzwony, był proboszczem w Złotej, leżącej w gminie Czchów.
Kiedy ks. Czekaj (szerzej piszemy o nim w haśle poświęconym wsi Królowa Górna), parający się również restauracją zabytków religijnych, czyścił akcesoria kościelne, odkrył, że malarzem leluchowskiego ikonostasu był w 1873 r. Wiktoryn Zomph (Zompf), urodzony w 1810 r. artysta, pochodzący z węgierskiego wówczas, a zamieszkałego przeważnie przez mieszczan niemieckich, dzisiaj słowackiego Bardiejowa. Właśnie w owym 1873 r. wykonanieIKONY
Chrystusa Nauczającego osobno opłacił kolejny potomek Krynickich – Aleksander z żoną Jeleną, o czym świadczy napis cyrylicą na jej odwrocie, który zobaczymy po wejściu za carskie wrota.
Odkrycie ks. Czekaja unieważniło dotychczas pokutujące przekonanie, że twórcami rokokowo-klasycystycznego ikonostasu byli w 1895 r. malarze Antoni i Michał Bogdańscy. Natomiast to nie Zomph wymalował w kościele całą polichromię, bo jest ona wcześniejsza, choć może przyłożył rękę do odnowienia jej fragmentów.
Po wysiedleniu Łemków, jesienią 1947 r. do składnicy muzealnej w Muszynie zwieziono wyposażenie 36 okolicznych cerkwi: całe zabytkowe ikonostasy, pojedynczeIKONY, ołtarze, rzeźby, starodruki, krzyże, świeczniki oraz inne sprzęty religijne. Z Leluchowa pochodziły 23 obiekty, w tym m.in. XVII- i XVIII-wieczne ikony Hodegitrii (jedna z I połowy XVII w., druga z 1653 r., trzecia z XVIII w.), Pankratora, św. Dymitra oraz liczne apostołów, ponadto barokowe carskie wrota. W 1949 r. zabytki te znalazły się w magazynie Muzeum Okręgowego w Nowym Sączu, a dopiero w 1965 r. urządzono z nich ekspozycję sztuki cerkiewnej z Łemkowszczyzny.
Drewniany kościół został odnowiony w latach 2004-2007, a polichromia w 2008 r. W wieży kościelnej bytują podkowce małe. O koloniach tego zagrożonego wyginięciem gatunku nietoperzy piszemy w hasłach poświęconych Bukowcowi i Królowej Górnej. Jednak ta w Leluchowie zajmuje trzecie miejsce w Polsce pod względem liczebności – w lipcu br. naliczono ich aż 250 sztuk.
W Dubnem znajduje się kościół pomocniczy pw. św. Michała Archanioła, co nie zmieniło się od czasów łemkowskich, bo taki sam tytuł miał także jako cerkiew zbudowana w 1863 r. na miejscu poprzedniej z 1673 r., która spłonęła.