Historia parafii Bełżec zaczyna się z początkiem XX wieku. Wcześniej miejscowość należała do parafii św. Andrzeja w Lipsku, dekanat Narol, archidiecezja lwowska. W 1901 roku w centrum Bełżca dokładnie na dzisiejszej drodze prowadzącej do cmentarza, kilkanaście metrów od szosy powstaje drewniana kaplica. Poświęcona w 1902 r. funkcjonuje jako świątynia filialna parafii Lipsko. W kronice tejże parafii na str. 13 czytamy: „… dnia 1 listopada 1909 r. objął obowiązki wikarego Ks. Zdzisław Łuczyński, jako ekspozyt w Bełżcu”.
Pierwszym duszpasterzem i organizatorem parafii, mieszkającym na stałe w Bełżcu był Ks. Jan Kątek. Obsługuje drewniany Kościółek, do którego dojeżdżali dawniej księża z Lipska. Mieszkając prywatnie buduje murowaną plebanię na gruncie zakupionym przez parafian. W 1911 r. rozpoczyna budowę nowego kościoła. Kościół usytuowano na gruntach pomiędzy zabudowaniami chłopskimi, a ogrodami dworskimi na wschód od drewnianego Kościółka. Nowy kościół zbudowano na planie krzyża łacińskiego, jednonawowy ze sklepieniem kolebkowym, na podmurówce kamiennej. Nosi on cechy stylu neoklasycystycznego. Fasadę świątyni zdobią umieszczone w półokrągłych wnękach, nawiązujących do kształtu okien, figury, oraz napis „Gloria in excelsis Deo”. We wnętrzu są trzy drewniane ołtarze i ambona pochodzące z okresu budowy świątyni, nawiązujące stylem do baroku. Ołtarz główny z obrazem Matki Bożej Królowej Polski patronki parafii, malowany na płótnie z ozdobną sukienką, zasłaniany bywa innym obrazem przedstawiającym „Scenę pod krzyżem”, również malowanym na płótnie. Z lewej i z prawej strony obrazu drewniane figury świętych biskupów Stanisława i Wojciecha. Nad obrazem Matki Bożej drewniana rzeźba przedstawiająca scenę walki św. Michała Archanioła ze smokiem. W ołtarzach bocznych obrazy Najświętszego Serca Pana Jezusa i św. Józefa z Dzieciątkiem. W sąsiedztwie kościoła znajduje się współczesna mu dzwonnica z trzema dzwonami.
W trakcie budowy kościoła odchodzi z pracy w parafii Bełżec Ks. Kątek, na jego miejsce w 1912 r. proboszczem zostaje Ks. Franciszek Rachel. Prace przy budowie trwają nadal, a w 1912 r. nowo zbudowany kościół zostaje poświęcony przez Księdza Biskupa Władysława Bandurskiego sufragana ze Lwowa. Następne lata to czas wyposażania wnętrza kościoła. Między innymi wówczas zaprojektowano w jednym stylu i wykonano trzy ołtarze drewniane i ambonę. W 1919 r. odchodzi Ks. Rachel, a jego miejsce zajmuje Ks. Jan Kijas. W tym czasie sprowadzono do kościoła 12 głosowe organy firmy Wacław Biernacki z Wilna, oraz zakupiono dzwony.
Od 1939 r. administratorem parafii jest Ks. Ireneusz Kmiecik, były prowincjał Ojców Reformatów. Prześladowany przez okupantów niemieckich jest świadkiem profanacji świątyni, którą zamieniono na magazyn, a dzwony zarekwirowano. Ksiądz mieszka na plebanii, która w większej części zajęta była przez wojsko. Nabożeństwa odprawiano nie opodal w opuszczonej cerkwi grecko-katolickiej. Po wojnie świątynia zostaje doprowadzona do porządku, a Ks. Kmiecik powraca w 1947 r. do klasztoru.
W latach 1947 – 1965 duszpasterzem jest Ks. Kan. Izydor Zmora. Wygnany z Żółkwi zabezpieczył i przywiózł do Bełżca przedmioty liturgiczne. W swej pracy zatroszczył się o pokrycie kościoła nową blachą, oraz sprawił dwa nowe dzwony w miejsce zabranych przez okupanta. Umiera 22.08.1965 r., pochowany na miejscowym cmentarzu. W latach 1965 – 1998 proboszczem jest Ks. Kan. Stanisław Węglowski. W tym czasie pokryto ściany polichromią, ufundowano witraże w oknach na prezbiterium, powstają: ołtarz soborowy z ambonką, ławki i konfesjonały. W latach 1988 – 1996 powstaje nowa plebania. Najważniejszym religijnym wydarzeniem tego okresu były uroczystości Nawiedzenia NMP w symbolach świecy i ewangelii 6 – 7 sierpnia 1971 r., na których byli obecni m.in. Ks. Kard. Karol Wojtyła i Prymas Polski Ks. Kard. Stefan Wyszyński.
W latach 1998 – 2007 proboszczem jest Ks. Bogdan Ważny, natomiast od roku 2007 jest nim Ks. Stanisław Szałański.
Z racji 100-lecia istnienia parafii w Bełżcu Ksiądz Biskup Wacław Depo 1 listopada 2009 r. dokonał poświęcenia odrestaurowanej dzwonnicy wraz z trzema dzwonami, oraz odnowionej zewnętrznej elewacji kościoła łącznie z drzwiami, a także wymienionego pokrycia dachu. Prace remontowe z racji setnej rocznicy istnienia parafii zostały wykonane w 2009 roku.
