Trudno określić czas powstania parafii. Zapewne istniała ona już w XV wieku. Z biegiem lat jej teren uległ zmniejszeniu na skutek powstawania w sąsiedztwie nowych parafii (m.in. Teratyn, Werbkowice, Nieledew). W czasie swego istnienia była dobrze uposażona w ziemię ( już w XVI wieku posiadała ona 1 łan ziemi), obecnie posiada 4,17 ha. W swojej historii przez długi czas należała do dekanatu hrubieszowskiego a obecnie do grabowieckiego. Na tym terenie mieszkali również grekokatolicy, którzy posiadali swoje parafie w Mołodiatyczach i Nieledwi. Zniesiono je w momencie kasaty unii a na ich miejsce powstały cerkwie prawosławne.
Źródła historyczne podają, że w byłym powiecie horodelskim były najważniejsze dwie miejscowości: miasto Horodło (ośrodek parafii rzymsko-katolickiej od 1425 roku) i wieś Trzeszczany (już wtedy również siedziba władz duchownych na szczeblu parafii). Kto był założycielem parafii i kto zbudował pierwszy, drewniany kościół – nie wiadomo. Wiemy tylko, że ten oraz prawdopodobnie drugi kościół z około 1606 r. spłonęły podczas najazdów tatarskich.
W 1687 r. powstał nowy, trzeci z kolei, drewniany kościół pod wezwaniem Wszystkich Świętych. Była to konstrukcja wieńcowa, bezwieżowa, na podmurówce ceglanej, kryta gontem. Kościół ten był orientowany, trójdzielny, złożony z małej kruchty, dużej nawy na rzucie kwadratu, długiego prostokątnego prezbiterium zamkniętego trójbocznie oraz przylegających do prezbiterium z dwóch stron: skarbczyka i zakrystii. Zrąb nawy i prezbiterium były równej wysokości, pokryte stropami. Z zewnątrz bryła zróżnicowana, z niską kruchtą, typowa dla kościołów bezwieżowych. Dach nad kruchtą i nawą był dwuspadowy, nad prezbiterium wielopołaciowy. W połowie długości kalenicy dachu nawy ustawiona była wieżyczka – sygnaturka, nakryta cebulkowatym hełmem zwieńczonym krzyżem. Kolejne najazdy tatarskie ocaliły go właśnie ze względu na umieszczony w sygnaturce pod krzyżem półksiężyc. Oszczędził go również Potop Szwedzki. To tutaj po Konfederacji Tyszowieckiej król Jan Kazimierz słuchał Mszy św. i pozostawił relikwie świętych. Upamiętniał to napis wyryty w prezbiterium Joannes Casimirus Rex Polonais. W r. 1937 został rozebrany i przewieziony do Chmiela (dekanat piasecki). Poniżej- widok obecny kościoła w Chmielu.
Cmentarz grzebalny był po prawej stronie kościoła. Później, w XVIII wieku ufundowano nowy cmentarz przy drodze Mołodiatycze- Trzeszczany. W tamtym czasie do Koscioła należało 300 morgów ziemi które były bogatym zapleczem parafii. Gdy nastały rozbiory Polski a wraz z nimi prześladowania religii katolickiej, dzieci chrzczono po kryjomu, śluby zawierano w odległej Częstochowie. Po śmierci ks. Moresińskiego carat zlicytował cały majątek a ziemię rozdał chłopom, którzy służyli 25 lat w wojsku carskim. Z tego czasu zachowało się wiele zabytków sztuki sakralnej. Parafian przybywało a ówczesny kościół nie mieścił wszystkich wiernych. Wszczęto więc starania o budowę nowego, murowanego kościoła, ale władze carskie nie wydawały zgody. W takiej sytuacji ówczesny dziedzic Trzeszczan Wydzga poczynił znaczne inwestycje wokół istniejącego kościoła: pobudował murowaną dzwonnicę, zakupił dzwony, ogrodził kościół murowanym płotem, zbudował nową plebanię oraz organistówkę które zachowały się do czasów obecnych. W 1905 roku władze carskie ogłosiły tolerancję religijną. W 1906 roku kościół wizytował ks. Biskup Jaczewski. Nastąpiły masowe powroty Rusinów do kościoła rzymsko- katolickiego. Ponownie zaczęto zabiegać o pozwolenie na budowę nowego, większego kościoła. Carat jak tylko mógł utrudniał wydanie zezwolenia. Poparł natomiast budowę cerkwi przy drodze Trzeszczany- Chyżowice. Dopiero pod presją okolicznej szlachty wydano zezwolenie pod warunkiem wcześniejszego wpłacenia 25.000 rubli w złocie. Jak głoszą ustne podania – carat widząc , jak wielkim wyzwaniem dla ludzi będzie postawienie tegoż kościoła, zgodził się w nadziei, że i tak nigdy nie uda im się go wybudować. Stało się jednak inaczej.
Obecny kościół pw. Trójcy Przenajświętszej i Narodzenia NMP z lat 1913-1924, został wybudowany wg projektu architekta Stefana Szyllera. Parafianie ofiarnie pomagali zwożąc wapno z odległej Bukownicy, cegłę z Hrubieszowa i z cegielni Crauzego, piasek z Zadębiec. Budowie tej nie mógł podołać ówczesny proboszcz, ksiądz Ostrowski. Nastał więc ksiądz Wacław Czechoński – młody i energiczny. Stworzył Komitet Budowy złożony z młościan popierany przez dwory. Dziedzice: Bielski, Tuszowski, Świerzawski zarządzali budową. I Wojna Światowa przerwała prace budowlane. Dzwony i pieniądze przeznaczone na budowę kościoła wywieziono w głąb Rosji do Kazania. w 1918 roku Polska odzyskała niepodległość więc ruszyła budowa kościoła. Prace budowlane przejął mistrz Szłapczyński z Zaklikowa. Powstały piękne mury, wieżyce, sklepienia. Wszystkie prace wykonywano ręcznie. Więźbę dachową wykonał mistrz Haczkiewicz z Horodła a drzwi – stolarz Marciniak z Lublina. Krzyże na wieży i zamki do drzwi- ślusarz z Zamościa, roboty blacharskie- firma z Warszawy. I tak, dzięki energii księdz proboszcza Wacława Czechońskiego, w 1921 roku przeniesiono się do nowego kościoła pod wezwaniem Narodzenia NMP. Poświęcenia dokonał ks prałat Juściński. Kościół został konsekrowany 8 VI 1924 r. przez biskupa Adolfa Jełowickiego. Sprowadzono dzwony. Nowe ołtarze ufundował dziedzic Jan Bielski.
Staraniem ks Floriana Gąsiorowskiego i dworów wybudowano schody do nowego kościoła i frontalne oparkowanie. W 1942 roku Niemcy zrabowali dzwony, ocalała tylko sygnaturka. Staraniem ks. Wojciecha Zwolaka zakupiono nowe dzwony. Następnie zakupiono organy, odnowiono tynki i założono instalację elektryczną.
Po śmierci ks Zwolaka nastał ks Józef Kuśmierczyk, który przeprowadził remont budynków gospodarczych, naprawił parkany kościoła i cmentarza. Zmodernizowano plebanię i wykonano osuszenie kościoła. W 1970 r.świątynia została uszkodzona przez huragan, później w 1975 r. uszkodzeniu uległa wieża. W 1971, 1985 i 1990 roku przeprowadzano kolejne renowacje dachu. Kościół jest usytuowany powyżej miejsca, gdzie stały poprzednie, czyli na szczycie wzgórza, które dominuje nad wsią. Ma on 40 m długości, 24 m szerokości, zaś wieża – 55 m wysokości. Jest on rzadkim przykładem stylu neogotyckiego na zamojszczyźnie. Obiekt nieregularnością bryły nawiązuje do romantycznej wersji neogotyku, mającej źródło w XIX wieku. Natomiast ceglaną fakturą nieotynkowanych elewacji łączy się z tradycją nurtu gotyku nadbałtyckiego. Kościół jest zbudowany z cegły, dachy są pokryte blachą miedzianą. Jest orientowaną, trójnawową halą z pięcioprzęsłowymi nawami, na rzucie wydłużonego prostokąta. Ma wysoką wieżę wyrastającą w północno-zachodnim narożniku korpusu posiadającą rzut kwadratu; jest pięciokondygnacyjna, w dole czworoboczna a w najwyższej kondygnacji ośmioboczna i zwieńczona smukłą iglicą. Prostokątne prezbiterium z trójboczną absydą. Korpus świątyni jest o połowę niższy od wieży, pokrywa go dwuspadowy dach. Po bokach wschodniego szczytu korpusu ujmują go dekoracyjne sterczyny w formie wieżyczek, a z wierzchołka wyrasta wieżyczka sygnaturki. Prezbiterium jest niższe i węższe od korpusu, dwuprzęsłowe, nakryte dachem dwuspadowym, a nad absydą trójpołaciowym. Kaplica i zakrystia, usytuowane po obu stronach prezbiterium są z kolei niższe od prezbiterium i osłonięte dachami pulpitowymi. W kościele występują zróżnicowane sklepienia: krzyżowo – żebrowe w nawach, prezbiterium oraz zakrystii i kaplicy; w kruchtach gwiaździste, a kolebkowe w przedsionku kruchty głównej.
W neogotyckim ołtarzu głównym – figury przedstawiające Trójcę Świętą oraz scenę ukoronowania Najświętszej Maryi Panny. Z lewej strony ołtarz ze statuą Chrystusa Króla i obrazem św. Franciszka z Asyżu oraz relikwiami św. Jana Pawła II. W kaplicy ołtarz z obrazem św. Teresy. Ławki i konfesjonały – neogotyckie, pochodzą z 1939 i 1960 roku.Najnowsze ławki w nawie głównej zostały wykonane w 2005 roku. Z poprzedniego kościoła zachowane częściowo wyposażenie: Prospekt organowy z XVIII wieku- na chórze muzycznym 22-głosowe organy wykonane w 1961r. i chrzcielnica neogotycka z 1953r.
Przy kościele dzwonnica neogotycka, wybudowana w 1974 r., 3 dzwony wykonano w 1948 r. w firmie Felczyńskich z Przemyśla (w 1948 r. święcił je bp Stefan Wyszyński).
Parafia pw. Trójcy Przenajświętszej i Narodzenia NMP w Trzeszczanach 