Akt fundacji pierwszego, drewnianego kościoła pw. Trójcy Przenajświętszej, św. Anny i św. Mateusza Ewangelisty w Wyrozębach, zwanych w XV wieku Wierozuby/Werozuby lub Wirozembi (XVI wiek), został sporządzony 16 listopada 1438 r. Dokonali go bracia: Marcin, Piotr i Paweł Wyrozębscy h. Jastrzębiec, dziedzice wsi Wyrozęby. Nowy kościół konsekrował w 1445 r. ks. Andrzej z Płońska, zwany w późniejszej historiografii Spławski (zm. 1459 r.), biskup włodzimierski i łucki (1425-59). W latach 1472-75 plebanem tegoż kościoła był ks. Wojciech, a w latach 1480-86 ks. Piotr. Kolatorami wyrozębskiego kościoła do XIX wieku były rodziny: Wyrozębskich, Mleczków ze Szkopów (ok. 1624 r.), Kunat-Wyrozębskich (od 1698 r.), Woronieckich z Huszlewa (1730-93), Kobylińskich ps. „Książko” (od 1793 r.), Olszańskich i Markowskich (1839 r.) oraz Dernałowiczów (od 1858 r.).
Pomiędzy rokiem 1700 a 1737 kosztem dziedziców Huszlewa (od 1737 r.) - Franciszka Korybuta ze Zbaraża Woronieckiego (zm. 1773 r.) i jego żony (od 1725 r.) Joanny z Wyroząb Kunat-Wyrozębskiej (ok. 1690-1760) został zbudowany kolejny, drewniany kościół. Świątynia została wzniesiona naprzeciwko obecnej, po drugiej stronie drogi. W 1752 r. spaliły się zabudowania plebańskie. Z kolei w czasie wojny napoleońskiej w 1813 r. kościół w Wyrozębach został poważnie ograbiony i zniszczony przez wojska austriackie.
Obecny murowany kościół, według projektu arch. Henryka Marconiego (1792-1863), został zbudowany w latach 1858-65 kosztem Tadeusza Doria Dernałowicza (1794-1862), właściciela klucza repkowskiego (od 1806 r.). Po śmierci fundatora budowę wspierała jego córka Ewa Maria Konstancja Teresa (1844-1907) oraz zięć - Seweryn Doria Dernałowicz (1833-1924). Kamień węgielny poświęcił 8 maja 1858 r. o. Beniamin Piotr Szymański OFM Cap. (1793-1868), biskup podlaski (1857-67). Budowę prowadzili: arch. Ludwik Jabłoński, budowniczy powiatu siedleckiego (1813-74), oraz ks. kan. Julian Brześciański (1821-1909), ówczesny proboszcz (1849-1909). On też, z upoważnienia biskupa podlaskiego, dokonał 26 listopada 1865 r. poświęcenia nowej świątyni.
W kościele w Wyrozębach 8 stycznia 1843 r. został ochrzczony Stefan Aleksander Zwierowicz h. Ancuta (1842-1908), syn rządcy z Repek, późniejszy biskup wileński (1897-1902), a następnie sandomierski (1902-08).
W latach 1891-1919 do Wyroząb była przyłączona parafia Paprotnia, która została w tym okresie skasowana przez rząd carski.
Przy kościele parafialnym w Wyrozębach nakładem Tadeusza i Seweryna Doria Dernałowiczów wybudowano w latach 1862-73 szpital - Intytut Dobroczynności pw. św. Judy Tadeusza. Na rzecz tegoż szpitala Tadeusz Doria Dernałowicz zapisał w 1862 r. folwark w Wyrozębach. Do 16 kwietnia 1887 r. Instytut Dobroczynności prowadziły Siostry Miłosierdzia św. Wincentego à Paulo (Szarytki). Po usunięciu ich przez rząd carski, zostały przysłane mniszki prawosławne (Elżbietanki), które przebywały w szpitalu do 17 stycznia 1906 r. Dzięki staraniom wspomnianego ks. Juliana Brześciańskiego oraz wnuka fundatora - Stanisława Doria Dernałowicza (1879-1918) w 1908 r. Siostry Szarytki powróciły do Wyroząb. Fundacja szpitala została upaństwowiona w 1952 r. Siostry pracowały tutaj do 1995 r.
Po przeciwnej stronie ulicy znajduje się murowana plebania, zbudowana przez ks. Czesława Sudoła (prob. 1986-92), którą wykończył ks. Tadeusz Sosnowski (prob. 1998-2002).

Bibliografia:
Archiwum diecezjalne w Drohiczynie. III /Q/. Akta parafii Wyrozęby 1885-1981. 1983-1987; P. Aleksandrowicz, Diecezja siedlecka, czyli podlaska, Sadowne 1956; B. Błoński, Fundacja kościoła parafialnego w Wyrozębach z r. 1438, Siedlce 1998 (mps); tenże, Zarys dziejów miejscowości Wyrozęby, w: Historia i tradycje ziemi najbliższej - Wyrozęby w gminie Repki, Sokołów Podlaski 2003, s. 7-35; B. Czarnocki, Ks. Julian Brześciański - życie i działalność, w: Historia i tradycje ziemi najbliższej - Wyrozęby w gminie Repki, Sokołów Podlaski 2003, s. 59-65; I. Galicka, H. Sygietyńska, Województwo warszawskie. Powiat sokołowski (Katalog zabytków sztuki w Polsce t. X, z. 25), Warszawa 1965; M. Głowacki, Katalog duchowieństwa i parafii diecezji siedleckiej, czyli podlaskiej, Siedlce 1985; Katalog kościołów i duchowieństwa diecezji siedleckiej, czyli podlaskiej na rok 1929, Siedlce 1929; B. Niemirka, Cmentarze w Wyrozębach jako fragment historii naszej „małej ojczyzny”, w: Historia i tradycje ziemi najbliższej - Wyrozęby w gminie Repki, Sokołów Podlaski 2003; s. 26-48; S. Ulaczyk (oprac.), Rocznik diecezji drohiczyńskiej. Spis parafii i duchowieństwa 1999, Drohiczyn 1999; K. Wolski, Jubileusz parafii Wyrozęby, Niedziela. Kościół na Podlasiu nr 38 z 1995 r., s. 11.

Porządek Mszy św.:
niedziele i święta:
- kościół parafialny: 9.00, 11.00
- kaplica w szpitalu: 7.30
święta niebędące dniami wolnymi od pracy:
- kościół parafialny: 9.00, 11.00
- kaplica w szpitalu: 7.30

Odpusty w parafii: Trójcy Przenajświętszej, św. Mateusza
Nabożeństwo adoracyjne: 6-8 grudnia

Księgi metrykalne:
Księgi chrztów: od 1608 r.
Księgi małżeństw: od 1766 r.
Księgi zmarłych: od 1753 r.