W marcu 1994 r. z inicjatywy proboszcza w Chotyńcu ks. Bogdana Stepana zakupiona została działka budowlana w Gajach na potrzeby miejscowych grekokatolików. 1 sierpnia 1994 r. bp Jan Martyniak wydał dekret erekcyjny na nową parafię greckokatolicka w Gajach pod wezwaniem Zaśnięcia Najświętszej Marii Panny. Pierwszym proboszczem nowopowstałej parafii został ks. Bogdan Stepan.

15 października 1966 r. na działce parafialnej w Gajach rozpoczęto prace budowlane przy wznoszeniu nowej świątyni. Do połowy listopada założono fundamenty, a w kwietniu następnego roku przystąpiono do wznoszenia murów. 16 czerwca 1997 r. o godz. 17.00 abp Jan Martyniak poświęcił kamień węgielny pod nową cerkiew.
W 1999 przeniesiono tu z cerkwi w Olchowcu ikonostas autorstwa Andrzeja Stefanowskiego z Zielonej Góry (powstał w 1989).
27 sierpnia 1999 r. ks. Bogdan Stepan odprawił pierwszą Liturgię w jeszcze nie poświęconej cerkwi. Konsekracji nowo wybudowanej świątyni dokonał abp Jan Martyniak w dniu 25 września 1999 r.

Porządek nabożeństw: niedziele i święta: 10:00

_{Na podstawie: www.grekokatolicy.pl}