Находится в 3-ей части города, в нескольких саженях от реки Западной Двины (близко к центру города).
Здание церкви сооружено около 1774 года армейскими войсками г. Витебска, а впоследствии была откуплена Витебским гарнизонным батальоном *). Со времени построения по 1852 г. состояла сначала в ведении Обер-Священника, а затем - главного Священника Армии и Флотов. Потом, по ветхости, была упразднена и передана в Епархиальное ведомство. В 1853-55 гг., по ходатайству жителей г. Витебска, возобновлена на средства ее собственные, а также ассигнованные Военным Министерством и на доброхотные пожертвования некоторых жителей города. В 1863 году церковь вновь перечислена в ведение Главного Священника Армии и Флотов и два года состояла при Батальоне внутренней стражи. С 1865 г. до 1889 года была при Управлении Витебского Уездного воинского начальника; в 1889 году причислена к 21-му резервному пехотному (кадровому) батальону, переименованному в Динабургский; затем была в ведении Управления 41-й Артиллерийской бригады, а с 1910 года и до настоящего времени - при Управлении Витебского Уездного воинского начальника.
Здание церкви - деревянное, на каменном фундаменте, вмещает до 500 душ; снаружи обшитое тесом и окрашенное масляною краскою, а внутри оштукатуренное и расписанное художественными орнаментами. Св. Престолов - два. Прихожанами храма состоят воинские чины Витебска, не имеющие штатных священников.
По штату при церкви положены: один священник и псаломщик. Квартира священнику казенная.
Г.А. Цитович "Храмы армии и флота". Пятигорск, 1913
*) Священник Витебской военной Николаевской церкви О. Никита Белороссов участвовал в войне 1812 года и, спасая церковное имущество от нашествия французских войск, не только лишился всего своего состояния, но и был в схватке ранен, в воздаяние чего ему было выдано единовременное пособие 350 руб. и пенсион.