Dzieje Podlasia były zawsze w jakiś sposób związane z historią Polski. Każdy kto opisywał losy ojczyzny, nie pomijał Podlasia, ale ukazywał go jako integralną część naszego kraju. Parafia Suchożebry należy do najstarszych parafii południowo-zachodniego Podlasia. Tereny, na których erygowano parafię Suchożebry, miały w średniowieczu charakter niespokojnego pogranicza i były miejscem licznych najazdów Rusinów, Jadźwingów, Litwinów. Pierwotnie należały do Polski, później do Rusi, Litwy, a po Unii lubelskiej w 1569 r. do Królestwa Polskiego. Przez wiele stuleci wzdłuż odległej o kilka kilometrów rzeki Liwiec, przebiegała granica pomiędzy Polską a Litwą a także Mazowszem i Podlasiem. Na tych terenach ścierały się fale kolonizacyjne różnych narodowości oraz działalność misyjna różnych zakonów. Dopiero pod koniec wieku XIV i w początkach XV, tworzą się sprzyjające warunki polityczne i społeczno-gospodarcze. Podlasie staje się łącznikiem między Litwą a Koroną, z krainy misyjnej przemienia się w autentyczną prowincję kościelną, będącą częścią składową archidiakonatu brzeskiego, należącego do diecezji włodzimiersko-łuckiej.
W roku 1422, Trojan Suchożebrski dziedzic z Suchożebrów przy poparciu szlachty z dziesięciu okolicznych wsi szlacheckich, wybudował drewniany kościół i doprowadził do utworzenia parafii. Źródła podają, że pierwotny kościół p.w. św. Marii Magdaleny był wzniesiony obok obecnego i posiadał plan krzyża łacińskiego. Ten doniosły czyn Trojana Suchożebrskiego i szlachty suchożebrskiej miał miejsce w dwanaście lat po bitwie pod Grunwaldem i w dziesięć po Unii Horodelskiej (1413 r.). Zachowany dokument mówi nam: „Akt erekcyjny fundacji zaginą i do dnia dzisiejszego nie został odnaleziony i stąd nie znamy wszystkich szczegółów tego przedsięwzięcia. Tylko z innych odwołań się na ten akt, wiemy, że taki dawniej istniał”.
W tym czasie Podlasie należało do Litwy i diecezja parafii była w Wilnie. Należy przypuszczać, że Trojan Suchożebrski ówczesny właściciel folwarku w Suchożebrach, był człowiekiem dość zamożnym, pobożnym i pełnym inicjatyw.
Jak z niektórych dokumentów wynika, nie był on w tym przedsięwzięciu sam, pomagała mu zagonowa szlachta zamieszkała w Suchożebrach, z nim spokrewniona spokrewniona liczebnie rodzina Podniesińskich z Podnieśna, która by zostać członkiem fundacji i mieć udział w zarządzie Rada Parafialnej dała w tym celu nawet kawałek gruntu. Ustalono przywilej, że każdy nowy członek fundacji może przyjąć nazwisko Suchożebrski. Należy sądzić, że niektórzy z tego przywileju skorzystali, bo w połowie siedemnastego wieku ponad połowa rodzin szlacheckich w Suchożebrach nosiła to nazwisko.
W 1580 roku parafia Suchożebry należy do powiatu drohickiego i ma na swoim terenie dziesięć osad wiejskich. Pod koniec XVI wieku do parafii dotarli arianie i kalwini. Znaleźli tu swoich zwolenników i nawet na pewien okres przejęli kościół Jednak w niedługim czasie przewagę uzyskali wyznawcy wiary rzymsko-katolickiej i w 1605 r. innowiercy zwrócili go katolikom.
Szczęśliwie przetrwała w parafia czas najazdu, tzw. potopu szwedzkiego w 1655 roku. W wykazie księdza biskupa łuckiego Jana Stefana Wydźgi do Stolicy Apostolskiej, podaje się, że „Parafia Suchożebry jest nie uszkodzona przez Szwedów.”
W 1657 roku do Suchożebrów przybył oddział Kozaków, który ograbił kościół z cenniejszych przedmiotów, a księgi parafialne spalił. Z tej to przyczyny w archiwum parafialnym zachowane są akta chrztów, ślubów, pogrzebów dopiero od 1657 r. Pierwszym proboszczem po najeździe Kozaków był ks. Jan Zętkowski (1657-1671), który założył nowe księgi metrykalne i starał się otworzyć dokumenty prawne, na których opierała się egzystencja materialna kościoła.
Kolejni proboszczowie to: ks. Łukasz Nosakowski (1671-1672), ks. Kazimierz Kadziński (1675-1689), ks. Adam Radus (1689-1690), ks. Józef Przygodzki (1690-1720), który remontuje kościół, budynki parafialne, porządkuje archiwum parafialne i zaprowadza rejestr snopowego, czyli tzw. dziesięciny należnej proboszczowi oraz spis poddanych proboszczowi pracowników rolnych, a także odpisy dokumentów darowizn, kontraktów i opis stanu majątku kościelnego. Ponadto tworzy szkółkę dla dzieci oraz osobne probostwo szpitalne, któremu zapisuje folwark Trojanki. Buduje domek dla dwóch księży ks. prepozyta, czyli kapelana szpitalnego i dla ks. promotora św. Różańca. Do kościoła dobudowuje kaplicę; jedną dla Bractwa św. Józefa i drugą dla Bractwa Różańcowego.
W okresie tzw. wojny północnej, rok 1710, zapoczątkował wystąpienie tzw. pomoru i kilku lat głodu. W ich wyniku wymarła większość mieszkańców w Suchożebrach, Przygodach, Sośnie i wielu innych wsiach. Nastąpiło masowe bankructwo zamożnej szlachty. Na dodatek wystąpiła plaga szczurów pustoszących okolice.
W latach 1720-1722 urząd proboszcza objął ks. Karol Woytkowski, a później przez 30 lat ks. Jan Borkowski. Okres był wyjątkowy trudny ze względu na ogromne zubożenie społeczeństwa w okresie niedawnych wojen, chorób i głodu. Za jego rządów odbyła się wizytacja generalna w 1737r. Zachował się protokół opisujący kościół jako drewniany w formie krzyża, pw. Św. Marii Magdaleny, przeszło 300 lat temu zbudowany. Ołtarz główny ze starym obrazem NMP Niepokalanie Poczętej. W jednej kaplicy ołtarz św. Antoniego i św. Józefa, a w drugiej św. Rocha i Najświętszego Serca Jezusowego, co świadczy o tym, że nabożeństwo do Najświętszego Serca szybko zaczęło się rozpowszechniać. W roku 1737 jest przy parafii Suchożebry szpital i zarazem przytułek pod kierownictwem księdza.
W latach 1736-1740 w Krześlinie należącym do parafii Suchożebry, zbudowano kościół i klasztor, który powierzono O.O. Dominikanom, a następnie O.O. Bernardynom.
Od 8 maja 1745 r. przez 49 lat proboszczem w Suchożebrach był ks. Andrzej Glinka. W tym czasie nastąpiło wiele zmian. Czasy coraz bardziej stabilizowały się, zagoiły się już rany powojennych zmaganiach. Tylko w parafii suchożebrskiej stary kościół liczący sobie już ok. 340 lat po remontach dokonanych przez ks. Józefa Przygodzkiego, ponownie uległ ruinie i praktycznie nie nadawał się do naprawy, widniała konieczność budowy nowego kościoła, aby dalej mogła istnieć parafia. Wsie ponownie zaludniły się i zagospodarowały, ale parafian nie stać było na budowę nowego kościoła.
W tym czasie dobra suchożebrskie tj. wsie Chodów, Wola, Kopcie i Suchożebry należały do posiadłości książęcej Czartoryskiej i stanowiły własność ich córki Aleksandry Ogińskiej zamieszkałej w Siedlcach. W tamtych czasach tylko księżnę jako właścicielkę dóbr suchożebrskich i siedleckich było stać i mogło zależeć na pobudowaniu nowego kościoła w Suchożebrach. Trudno już dziś ustalić kto był głównym pomysłodawcą i kiedy dokładnie się to działo, ale do dziś przetrwały ustne przekazy, przekazywane z pokolenia na pokolenie o tym fakcie. Mogło to być około 1766-68 roku, wówczas proboszczem w parafii był ks. Andrzej Glinka, nazwisko kościelnego nie zachowało się, ale był to człowiek bardzo śmiały i wymowny, i była w Suchożebrach z inicjatywą, której budowa kościoła leżała na sercu.
Dowiedzieli się oni, że Księżna wybiera się w podróż i będzie przejeżdżała przez Suchożebry.
Powołali z własnej inicjatywy wspólnie z ks. proboszczem delegację i za jego zgodą wybrali za przewodniczącego, rezolutnego kościelnego, ustalono tekst prośby z jaką wystąpił do Księżnej, przygotowano kwiaty i czekano na karetę. Przyjazd się opóźniał, wszyscy byli zniecierpliwieni, ale wreszcie kareta najechała i Księżna widząc delegację z kwiatami, która wyszła jej naprzeciw kazała zatrzymać karetę. W imieniu delegacji i parafian Księżnę powitał kościelny i przedstawił jej prośbę parafian, by pobudowała im nowy kościół, bo stary nie nadaje się do naprawy. Księżna była wzruszona powitaniem, wysiadła z karety, przyjęła kwiaty, poszła z delegacją do kościoła, a tam już przed drzwiami czekał ks. proboszcz, przywitał księżnę i wprowadził do kościoła, w którym tłum wiernych z chorągwiami również ją witał. Księżna była ponownie wzruszona i po obejrzeniu kościoła, gdy zobaczyła, że jest on zbyt zrujnowany wiekiem, chwilę zatrzymała się, a następnie po namyśle powiedziała zebranym, że pobuduje im nowy kościół, czym wszystkich zebranych parafian bardzo ucieszyła. Wszyscy jej szczerze dziękowali, byli jej wdzięczni i wzruszeni.
Stary kościół drewniany stał na miejscu obecnego starego cmentarza, a cmentarz był tu gdzie obecnie stoi kościół.
Przetrwały jeszcze przekazy, że gdy przodkowie niektórych obecnych mieszkańców kopali rowy pod fundamenty nowego kościoła, wykopywali kości ludzkie. Stary kościół stał i służył parafianom aż do ukończenia budowy nowego.
Niektórzy twierdzą, że pobudowany kościół był krótszy od obecnego o odcinek, w którym obecnie znajdują się wieże, inni twierdzą, że był on tej samej długości co obecny.
Budowę rozpoczęto w 1772 r. Cegłę wyprodukowano we własnym zakresie z gliny kopalnej na kościelnej łące za rzeką, gdzie do obecnych czasów pozostały jeszcze doły i tam wypalano cegłę. Strop kościoła był drewniany, a dach kryty czerwoną dachówką. Podłoga była drewniana z desek. Budowę zakończono w 1778 r. Wszystkie roboty niefachowe wykonywano w ramach odrabiania pańszczyzny, a szlachta pracowała w czynie społecznym.
Razem z kościołem została wybudowana kaplica, która w latach późniejszych aż do naszych czasów służyła za kostnicę, a na piętrze dawniej były umieszczone dzwony.
Księżna przez cały okres budowy interesowała się przebiegiem prac i sama własnoręcznie wmurowała kamień węgielny. Na ten temat przetrwały wspomnienia wśród ludności. Ksiądz Andrzej Glinka zmarł 8 czerwca 1794 r. i najprawdopodobniej został pochowany na cmentarzu w Suchożebrach.
Kościół został konsekrowany dopiero w 1837 r. przez biskupa Jana Marcelego Gutkowskiego.
W 1877 r. założono nowy cmentarz grzebalny w Przygodach. Administratorem parafii był wówczas ks. Józef Ostałowski, który 12 IX 1877 r. otrzymał pozwolenie na wyświęcenie nowego cmentarza. Cmentarz ten użytkowany jest do dnia dzisiejszego. Z pierwotnego cmentarza usytuowanego przy kościele, zachowało się jeszcze kilka nagrobków.
Na początku XX wieku kościół chciała dwukrotnie przejąć sekta mariawitów, ale zamiar ten udaremnili parafianie. W latach 1906-1912 staraniem ks. proboszcza Michała Dworzyckiego i prezesa dozoru kościelnego w Suchożebrach Jana Paprockiego, do korpusu kościoła dobudowano dwie wieże, zmieniono w stropie kościoła belki drewniane na żelazne, a nad prezbiterium strop zastąpiono sklepieniem, dach pokryto dachówką, natomiast posadzkę w kościele wykonano z płytek. Na zewnątrz od frontu dobudowano drugą kaplicę z przeznaczeniem na dzwonnicę.
W 1911 r. powstała parafia w Krześlinie. W jej skład weszły z parafii suchożebrskiej wsie: Borki, Kownaciska, Krześlin i Rzeszotków.
W czasie II wojny światowej Niemcy zarekwirowali wszystkie dzwony kościelne, których było cztery. Ocalał tylko jeden, dzięki temu, że został ukryty w sadzawce. W tym samym roku, w 1941, wybuchła w parafii epidemia tyfusu plamistego, z tego powodu władze zabroniły wnosić zmarłych do kościoła.
W następnych latach w parafii Suchożebry urząd proboszcza pełnili:
– ks. Rafał Łysanowicz 1947-1963
– ks. Stanisław Domański 1947-1965
– ks. Piotr Szpilewicz 1965-1971
– ks. Stanisław Mućko 1971-1975
– ks. Mieczysław Skorodziuk 1975-1983
– ks. Stanisław Sopulski 1983-1998
– ks. Stanisław Dadas – administrator parafii 1995-1998
– ks. Zdzisław Domański 1998-2014 – proboszcz i dziekan dekanatu suchożebrskiego
– ks. Kazimierz Chełstowski 2014-2024 – proboszcz i dziekan dekanatu suchożebrskiego
– ks. mgr Jacek Nazaruk od 1 lipca 2024 – proboszcz i dziekan dekanatu suchożebrskiego
W ostatnich latach przeprowadzono gruntowny remont kościoła: wymiana dachu na kościele i wieżach /pokrycie blachą miedzianą/, odnowiono kościół z zewnątrz i wewnątrz łącznie z oświetleniem kościoła.