Do parafii w Muszynie Leluchów należał przynajmniej od 1604 r., kiedy biskup krakowski Bernard Maciejowski przyłączył do niej 30 okolicznych wsi „schizmatyckich”, czyli prawosławnych i grekokatolickich. Do dzisiaj z powodu małej liczby mieszkańców nie ma tu parafii, lecz rektorat na jej prawach, obejmujący także Dubne.
Przez lata opiekę duszpasterską zapewniali księża, dojeżdżający z parafii św. Józefa w Muszynie. Zaraz po wysiedleniu Łemków do muszyńskiej parafii należało 17 rodzin z Leluchowa, a 13 z Dubnego. W 1990 r. utworzono samodzielny rektorat. Z powodu tego rektoratu rodziły się nieporozumienia. Bowiem kiedy w 2003 r. otwierano Most Wyszehradzki, to ówczesnemu premierowi Leszkowi Millerowi przedstawiono ks. Adama Świądera właśnie jako rektora. Zdezorientowany premier miał wtedy zażartować, że skąd taki mały Leluchów dorobił się uniwersytetu…
Rektorat w Leluchowie graniczy z parafią grekokatolicką w słowackim Circu. Właśnie ksiądz stamtąd dojeżdża do kościoła w granicznej Ruskiej Voli. Kiedyś parafia grekokatolicka w samym tylko Leluchowie była właścicielem 57 hektarów. Od 20 lat trwają starania o przejęcie tej ziemi. I na razie udało się z parunastoma hektarami lasu.