Parafia NMP Królowej Polski w Stawie to niewielka wspólnota. Należy do niej ok. 1,5 tys. mieszkańców. Informacji na temat jej początków można doszukać się w kronice parafialnej. W 1981 r. ówczesny proboszcz parafii Czułczyce ks. Marian Pastuszko zakupił od Henryka Szachuna dom, który przystosował na kaplicę. Pierwszą Mszę św. w kaplicy w Stawie odprawiono już po kilku miesiącach od rozbudowy. Od tego czasu Eucharystia była tam sprawowana w niedziele i święta. Gdy kaplica okazała się za mała na ówczesne potrzeby duszpasterskie wspólnoty, postanowiono wybudować kościół. Zakupiono plac, który już w 1983 r. poświęcił dziekan dekanatu Chełm-Wschód ks. Kazimierz Bownik.

 

Projekt kościoła wraz z pomieszczeniami mieszkalnymi stworzył architekt Wojciech Pałka. Dzięki temu, że w prace przy świątyni zaangażowało się wielu parafian, budowę zakończono w 1986 r. Kilka lat później, wiosną 1993 r., dekret erygujący parafię wydał abp Bolesław Pylak.

Terytorium nowej parafii zostało wyodrębnione z parafii Czułczyce, Podgórze oraz pw. św. Kazimierza w Chełmie. W jej skład weszły miejscowości: Staw, Krobonosz, Ochoża-Kolonia, Ochoża i Parypse.

​

Pierwszym proboszczem został ks. Ryszard Jabłoński. Kolejnymi proboszczami byli: ks. Dariusz Stankiewicz, ks. Jarosław Wójcik oraz
ks. Jerzy Koma.