Церковь на минском Военном кладбище была построена в 1896–1898 гг. в ретроспективно-русском стиле в память об ополченцах, погибших во время русско-турецкой войны 1877–1878 годов.
Внутри храма помещены мраморные плиты с именами 118 белорусских офицеров и солдат, павших при освобождении Болгарии в годы той войны. Минский пехотный полк первым форсировал Дунай, белорусы также отличились при взятии Шипки и в боях под Плевной. Ежегодно 3 марта (день обретения независимости Болгарией) в церкви проходят богослужения, на которых воины-освободители поминаются поименно.
Во время бомбардировки города немецкими самолетами в июне 1941 года одна из бомб, пробив купол святыни, упала перед алтарем — и не взорвалась. В годы «застоя» церковь Александра Невского была одним из двух действовавших тогда в Минске храмов.