Starania o utworzenie parafii w Tryczówce podjęli w 1921 r. mieszkańcy wsi należących do parafii w Surażu, Juchnowcu i Turośni Kościelnej, którzy ze względu na odległość mieli utrudniony dostęp do posługi duszpasterskiej. W 1924 r. powołano komitet budowy kościoła z proboszczem suraskim, ks. Bonifacym Oleszczukiem na czele. W 1925 r. komitet nabył drewnianą kaplicę z Czarnej Wsi i ustawił ją na zakupionym wcześniej placu. Zbudowano również plebanię. Parafię w Tryczówce erygował abp wileński Romuald Jałbrzykowski dokumentem wydanym w Wilnie 7 września 1928 r. (pervigiliis Nativitatis Beatae Mariae Virginis). Pierwszym proboszczem został ks. Stanisław Glakowski.
Budowę murowanej świątyni zainicjował w 1929 r. ks. proboszcz Alfons Borowski, a sfinansowali ofiarni parafianie. Projekt, nawiązujący do uproszczonych form romańskich, wykonał warszawski arch. Leonard Kario. Kościół wzniesiono z pustaków na rzucie prostokąta, jako salowy budynek z wieżą na osi, wysuniętą przed lico fasady. Po przeciwległej stronie zbudowano niższe od korpusu prezbiterium, ujęte dwiema zakrystiami. Korpus świątyni przykryto dwuspadowym dachem, a wieżę iglicowym dachem poderwanym. Dnia 6 lipca 1930 r. dziekan białostocki, ks. Aleksander Chodyko poświęcił kościół, a 18 października 1931 r. abp R. Jałbrzykowski uroczyście go konsekrował.
Podczas II wojny światowej kościół był dwukrotnie ostrzeliwany (w 1941 i 1944 r.). W latach 1949-1951 ks. Aleksander Grabowski wyposażył wnętrze kościoła, m.in. zbudował organy, które wykonała firma Zygmunta Kamińskiego z Warszawy. Po 1994 r. proboszcz, ks. Henryk Radziewicz razem z parafianami przeprowadził generalny remont świątyni. Wzmocniono wówczas fundamenty i ściany kościoła, budynek otynkowano, ocieplono wnętrze i wykonano jego nową aranżację.
Do parafii należą miejscowości: Tryczówka, Bogdanki, Baranki, Czerewki, Dorożki, Klewinowo, Kożany, Pańki, Rostołty, Ryboły, Rzepniki, Wojszki, Zajączki, Złotniki.
Liczba katolików: 760