Historia parafii rozpoczyna się 15 października 1922 r., kiedy to odbyła się benedykcja kościoła przez ks. Andrzeja Wadowskiego kanonika kolegiaty zamojskiej, dziekana i proboszcza szczebrzeszyńskiego. Wydarzenie to upamiętnia postument stojący na placu przykościelnym z napisem "Boże, któryś nam wraz z Ojczyzną miejsce to przywrócić raczył". Pierwotny budynek kościoła liczy sobie 100 lat, pozyskano go z drewnianej cerkwi prawosławnej wybudowanej w stylu rosyjsko-bizantyjskim w 1902 r. Początkowo pokryty gontem kościół był jednonawowy, składał się z prezbiterium, nawy, chóru, przedsionka, zakrystii (dobudowanej w 1923) i skarbca. Wewnątrz trzy drewniane ołtarze z drzewa sosnowego, główny wykonany z części ikonostasu z obrazem Matki Bożej Sokalskiej. W antypedium postaci 5 Apostołów na obrazach. Obok prezbiterium dwa prowizoryczne ołtarzyki - z lewej obraz Chrystusa, w drugim obraz Matki Bożej. Obraz św. Jana Chrzciciela zawieszony był na ścianie, a nad prezbiterium - obraz Ostatniej Wieczerzy. Na przełomie lat 1933/34 dokonano częściowej przebudowy, nawę przedłużono o dwa przęsła; kościół przebudowano i powiększono. Zrobiono z drewna ołtarz wielki (w nim umieszczono ruchome obrazy: Chrztu Chrystusa w Jordanie i św. Antoniego Padewskiego) oraz 2 ołtarze boczne. W roku 1955 zdjęto z środka kościoła starą (zgniłą) kopułę cerkwi i pobudowano nową wieżę w przedniej części nawy kościoła oraz wykonano chrzcielnicę.
Od 1996 r. parafią zarządza ks. kan. Julian Brzezicki, który jest 11. proboszczem tej parafii. Z jego inicjatywy wykonano wiele prac z wielkim zaangażowaniem parafian. Przeprowadzono kapitalny remont plebanii i wybudowano kotłownię na olej opałowy. Odbudowano z ruin organistówkę z przeznaczeniem na Dom Katolickiego Stowarzyszenia Młodzieży. Tablicę pamiątkową na Dom KSM, któremu nadano imię bł. ks. Zygmunta Pisarskiego, poświęcił Jan Paweł II w Zamościu 12 czerwca 1999 r. Uroczystego poświęcenia i otwarcia Domu dokonał bp Mariusz Leszczyński 7 listopada 1999 r. Odnowiono też świątynię parafialną, ołtarze i feretrony. Do cmentarza zrobiono drogę asfaltową i wytyczono parking.
Parafia ma swojego błogosławionego ks. Zygmunta Pisarskiego (13 czerwca 1999 r. Jan Paweł II ogłosił go błogosławionym wśród 108 męczenników II wojny światowej), który pracował tutaj od 2 maja 1930 r. do 8 lutego 1932 r. Nabył on do parafii m.in. stacje drogi krzyżowej, obrazy Serca Jezusa i Serca Maryi, figurę św. Franciszka, sygnaturkę, krzyż do zakrystii służące do dzisiaj.
W lipcu 1943 r. wioska została wysiedlona przez hitlerowców, a wraz z mieszkańcami do obozu przejściowego w Zwierzyńcu trafił ówczesny proboszcz ks. Józef Perskiewicz, który był dla parafian oparciem w czasie niedoli.
Wiele zmieniono w parafii za ks. Jana Mazura, więźnia obozu koncentracyjnego w Dachau, który był administratorem od 1953 r. - aż do śmierci w 1957 r. Najdłużej, bo 26 lat funkcję proboszcza parafii sprawował ks. kanonik Wacław Daruk (nadal mieszkający w Trzęsinach).
Szczególnym gościem parafii był biskup lubelski Stefan Wyszyński, który prawdopodobnie 13 czerwca 1947 r. odwiedził parafię. Świadek tego wydarzenia Stanisław Rapa jako ministrant witał biskupa w Czarnymstoku i pamięta, że biskup wziął go na kolana i razem jechali do Trzęsin. Biskup był uroczyście prowadzony przez bardzo liczną banderię konną od granicy parafii i tak samo odprowadzony.
Najstarsze dane z terenu obecnej parafii Trzęiny są o miejscowości Czarnystok-Ruś. Kroniki podają, że wieś została osadzona w 1536 r. przez Jana, Krzysztofa i Szczepana Latyczyńskich, którzy dali prawo na zamieszkanie w tym miejscu Sienkowi. W 1593 r. wioska położona we włości szczebrzeszyńskiej została włączona do Ordynacji Zamojskiej. W Słowniku geograficznym Królestwa Polskiego czytamy: "Z pagórka, zwanego Górą Trzęsińską, wydobywa się piaskowiec wapienny. Z niego były wzniesione mury twierdzy Zamościa" (również kościół na wodzie w Zwierzyńcu). W Czarnymstoku-Rusi istniała cerkiew unicka filialna należąca do parafii Tereszpol. W 1875 r. została zamieniona na prawosławną. Z czasem cerkiew rozebrano, a w miejscu tym postawiono murowaną kapliczkę, która stoi do dziś. Prawosławni pobudowali w 1902 r. drewnianą cerkiew w Trzęsinach, głównie dzięki staraniom mniszek osiadłych w zabranym przez rząd carski na rzecz prawosławia klasztorze ojców bernardynów w Radecznicy. Gdy w roku 1902 budowę ukończono, przy cerkwi zamieszkał pop w charakterze kapelana. Taki stan trwał do I wojny światowej. Kiedy armia rosyjska wycofała się pod naporem wojsk niemieckich i austriackich w 1915 r., pop wyjechał do Rosji, a cerkiew zamknięto. Po ustąpieniu Moskali postanowiono zamienić cerkiew na kościół katolicki, gdyż wyznawcy prawosławia byli nieliczni. Tereny obecnej parafii Trzęsiny należały wówczas do 2 parafii: Radzięcin i Szczebrzeszyn. Tak więc mieszkańcy wiosek: Trzęsiny, Czarnystok, Wólka Czarnostocka i Smoryń poczęli czynić starania, aby pustą cerkiew zamienić na świątynię katolicką. Za zachętą dziekana szczebrzeszyńskiego i gwardiana z Radecznicy o. Metodego Sikory wybrano komitet na czele z Antonim Olechem z Czarnegostoku, zlecając mu przygotowanie cerkwi, aby służyła jako kościół. Z początku ojcowie brenardyni przyjeżdżali w niedziele i święta odprawiać nabożeństwa, z czasem wystąpiono z prośbą do biskupa lubelskiego Mariana Fulmana o utworzenie w Trzęsinach parafii. Biskup mianował we wrześniu 1925 r. proboszczem tworzącej się parafii ks. Józefa Gładysza. W skład jej weszły wioski: Trzęsiny, Smoryń, Buczyn i część Kol. Teodorowskiej pod nazwą Budy Komodziańskie wydzielone z parafii Radzięcin oraz Czarnystok i Wólka Czarnostocka wydzielone z parafii Szczebrzeszyn. Początkowo parafia liczyła 1880 dusz, została uposażona w ziemię i przydzielona do dekanatu Szczebrzeszyn. Plebanię urządzono w dawnej szkole, a pierwszy budynek gospodarczy wybudowano w 1926/7 r.