Dopiero w XVI w. pojawiła się nazwa Vyski. Pierwotnie miejscowość ta nazwała się - Piórkowo lub Piórkow. Pierwszy drewniany kościół pw. Zwiastowania Najświętszej Maryi Panny, św. Andrzeja Apostoła, św. Anny i Znalezienia Krzyża Świętego został ufundowany w niedzielę przed świętem Męczeństwa św. Jana Chrzciciela, czyli 28 sierpnia 1457 r. Jego fundatorami byli właściciele wsi - Wisław z Piórkowa, (podsędek ziemski bielski) oraz jego bratankowie: Paweł, Tomasz, Andrzej, Stanisław i Jakub. Uposażenie kościoła stanowiły wówczas: dwie włóki ziemi, dwie łąki, wieś Kołby i młyn za Piórkowem. Pierwszym plebanem został ks. Andrzej, który występował w aktach Konsystorza Janowskiego do 1478 r. Po nim duszpasterzował ks. Stanisław Pełka (do 1542 r.). W 1498 r. posługiwano się już nazwą Wyszki, w miejsce dotychczasowej - Piórkowo. Ks. Paweł Algimunt książę Holszański (1485-1555), biskup łucki (1507-1536), 7 lipca 1522 r. wydzielił parafię wyszkowską z trzynastu wsi szlacheckich („okolic”).
Podczas potopu szwedzkiego kościół został ograbiony, a ks. Mikołaj Piekutowski, ówczesny proboszcz wyszkowski (1648-1665), ciężko raniony. W 1779 r. spłonęły najstarsze dokumenty i księgi.
W 1804 r. został zbudowany w kościele chór kosztem dziedzica Kiewłak - porucznika kawalerii narodowej Wojsk Polskich - Juliana Kiersnowskiego (1769-1813), sędziego grodzkiego brańskiego (1804) i sędziego ziemi bielskiej (ok. 1810-13) i jego żony miecznikowej Bogumiły z Kłanickich (1776-1810). Dobrodziejem kościoła w tymże roku był również parafianin wyszkowski Jan Niewiński (1774-1834) zwany „Białoszow” i jego żona Ewa (1792-1834) ufundowali ośmiogłosowe organy. W 1808 r. kościół oszalowano tarcicami. W 1857 r. został rozpoczęty generalny remont świątyni przez ks. Justyna Nikodema Ściepuszyńskiego (1805-80), proboszcza wyszkowskiego (1843-80). W latach carskich represji został on aresztowany i osadzony w więzieniu (27 września 1863 r.).
Pierwsza, drewniana świątynia została rozebrana w 1902 r. Tego samego roku 7 lipca rozpoczęto budowę murowanego kościoła pw. św. Andrzeja Apostoła pod kierunkiem ks. Wincentego Wojtekunasa - proboszcza wyszkowskiego (1901-07). Msze św. sprawowano wówczas w kaplicy w Pulszach lub w domu pogrzebowym. Uroczystego poświęcenia nowej neogotyckiej świątyni, dokonał 28 sierpnia 1905 r. ks. prał. Jan Kurczewski (1854-1914), kanonik Wileńskiej Kapituły Katedralnej. W tym też roku świątynia została konsekrowana przez ks. Edwarda Libera barona von Roppa (1851-1939), biskupa wileńskiego (1904-1907).
Podczas I wojny światowej wojska rosyjskie skonfiskowały dzwony, a sama świątynia została mocno uszkodzona podczas ostrzału artyleryjskiego. Po ustaniu działań wojennych, konieczne remonty przeprowadził ks. Bolesław Wincenty Jarocki (1868-1922), ówczesny proboszcz wyszkowski (1910-22). Pod koniec II wojny światowej wycofujące się niemieckie oddziały SS 30 lipca 1944 r. wysadziły wieże kościelne i zburzyły fronton, uszkadzając sklepienie i ściany. W prowizorycznie wyremontowanej świątyni od 26 lipca 1945 r. zaczęto odprawiać nabożeństwa. Jej odbudowa, którą rozpoczął ks. Izydor Niedroszlański (1887-1950), proboszcz wyszkowski (1930-48), trwała wiele lat i zakończono ją dopiero w 1961 r. Pracami kierował ówczesny duszpasterz (1948-62) ks. Tomasz Miłkowski (1906-63).
Obok kościoła stoi murowana plebania, zbudowana (w 1978-79 r.) staraniem ks. kan. Edmunda Tararuja (prob. 1977-85).
W Pulszach położona na starym cmentarzu (dawniej: Pulsy), znajduje się drewniana kaplica dojazdowa, pw. Przemienienia Pańskiego. Pierwsza kaplica pw. Trójcy Przenajświętszej i św. Stanisława Biskupa i Męczennika - jako kościół filialny - została wzniesiona przez ks. Stanisława Jacka Bolko h. Rogala (zm. 1624), proboszcza bielskiego (1604-24). Jej poświęcenia dokonał 18 listopada 1613 r. ks. Jan Szyjkowski (1721-98), proboszcz prepozytury bielskiej (1756-97), biskup tytularny Sinope, sufragan łucki okręgu brzeskiego. W 1848 r. kaplica ta spłonęła. Kolejna została zbudowana w latach 1849-50, staraniem miejscowej ludności. Od 1846 r. kaplica w Pulszach należy do parafii wyszkowskiej (wcześniej do Bielska Podlaskiego).

Porządek Mszy św.:
W niedziele i święta:

W święta nie będące dniami wolnymi od pracy:

Odpusty w parafii są 26 lipca - św. Anny, i 30 listopada - św. Andrzeja Apostoła

Nabożeństwo adoracyjne: 30 listopada - św. Andrzeja Apostoła i dwa kolejne dni.