Постройка церкви Милующей иконы Божией Матери началась в 1889 году в честь годовщины коронации императора Александра III, а закончилась в 1898 году. Решение построить церковь принадлежало Морскому ведомству — министерству управления военным флотом Российской империи. Поэтому церковь была построена неподалёку от моря, в Галерной гавани.

Расположение сыграло ключевую роль в участи храма в советский период. Сразу после закрытия в 1932 году его здание перешло в ведение отряда подводного плавания. В самом центре установили барокамеру для тренировок погружения с куполом, а позже — бассейн. Следствием этого стало полное уничтожение внутреннего убранства церкви. К концу ХХ века общее состояние здания стало критическим. Передача храма РПЦ случилась лишь в 2012 году, с 2015 года он закрыт на реставрацию.

Проект храма, созданный Василием Косяковым, исполнен в нововизантийском стиле. Уникальный облик храму придаёт необычное воплощение пятикупольной системы. Четыре боковых купола лишь наполовину выступают из центрального. А под барабаном каждого из куполов проходит цепочка переходящих друг в друга арочных окон.