Церковь была построена по образцовому проекту военных храмов, утверждённому Строительной комиссией в 1901 г. (арх. Ф.М. Вержбицкий). Всего в Российской Империи к 1917 г. было выстроено не менее 69 таких церквей.
Данный храм для расквартированного в Белостоке 64-го пехотного Казанского полка был освящён 30 ноября 1904 г. благочинным 16-й пехотной дивизии свящ. Александром Красовским во имя во имя Успения Пресвятой Богородицы. До постройки собственного полкового храма полк использовал для Богослужений походную Успенскую церковь. Белосток являлся единственным городом, где по данному проекту было сооружено два храма. Второй из них была полковая церковь 4-го Уланского Харьковского полка https://sobory.ru/article/?object=45517
В 1915 г. после ухода русских войск церковь была закрыта, а в 1921 г. обращена поляками в гарнизонный костёл Святого Сердца Иисусова. Спустя некоторое время храм был обезглавлен - удалены большая глава, малые главки и кокошники на боковых фасадах, шатёр колокольни заменён на остроконечный. При этом общий архитектурный объём здания был сохранён.
В 1946 г. костёл был отремонтирован и передан из военного ведомства в епархиальное, а 25.06.1973 г. реорганизован в самостоятельный приход. Торжественное освящение обновлённого костёла совершил 30.10.1994 г. епископ Станислав Шимецкий. В настоящее время костёл является действующим и имеет собственный сайт: http://www.nsj.bialystok.pl/
Источники: РГИА ф. 806, оп. 8, д. 199 (1909 г.); Цитовичъ Г.А. Храмы Армiи и Флота, 1913, с. 219