Основан князем Витовтом в 1430 году, и изначально освящен под титулом Святого Николая. С тех пор история костела написана огнем: сжигали крестоносцы, татары, но благодаря пожертвованиям прихожан, магнатов и шляхты его снова и снова отстраивали. Статус фарного тогда еще деревянный костел получил в 1511 году благодаря королю Сигизмунду I Августу. Примечательно, что в многочисленных пожарах деревянных костелов оставалась невредимой чудотворная икона Божьей Матери. Пожар 1827 года поставил точку в деревянных костелах Волковыска. Настала эра камня!

В стиле позднего классицизма и таким, каким видим мы сейчас костел в Волковыске, он появился 1848 г. по проекту Александра Грудецкого на средства прихожан, рода Сегеней и ксендза Яна Лениковского. Построен он был через дорогу от места предыдущих костелов, вместо корчмы.

В 1929 году в новом каменном костеле сгорело все деревянное. Сохранился только приходской архив и инвентарь ризницы. Архитектор Оскар Сосновский в своем проекте достроил колокольни в неоклассическом стиле, прямоугольную апсиду с лестницей в ложи для молитв над ризницей, интерьер был разделен на нефы тремя парами тосканских колонн. В 1931 году костел был второй раз освящен в честь Святого Вацлава (первый — в 1850 году епископом Вацлавом Жилинским).

В советское время в костеле не прекращались богослужения. После Второй мировой войны храм был восстановлен и службы продолжились. Объект включён в Государственный список историко-культурных ценностей РБ.

Отсюда