Деревянная церковь Перенесения мощей Св. Николая Чудотворца была основана в 1340 г. второй женой Великого князя Литовского Альгирдаса Юлианой. После уничтожения церкви пожаром в 1514 г. литовский гетман Константин Острогишкий построил каменную готическую церковь в византийском стиле. В 1609 г. согласно привилегии короля Сигизмунда Вазы униатам было передано 12 православных церквей, в том числе церковь Св. Николая.
После пожаров 1747 г. и 1748 г. церковь была обновлена в стиле барокко. В 1827 г. ее вернули православным. После восстания 1863 г. указом М. Муравьева многие храмы были закрыты. Во время проведения реформы русификации в 1845 г. церковь Св. Николая была перестроена в русском византийском стиле. Таковым храм сохранился до наших дней. Тогда был снесен жилой дом, а к церкви пристроены притвор и квадратная часовня Св. Архангела Михаила. В толще стены с внешней стороны часовни под густым слоем краски находится мемориальная доска, выражающая благодарность М. Муравьеву за наведение в крае порядка и покоя. Содержание этой надписи зафиксировано в исторической литературе конца XIX в.
В этой церкви вел службы отец известного русского актера - Василия Качалова, а сам он родился в доме рядом.