В 1847 году на месте, где ранее находилась деревянная церковь, сгоревшая на Сторожевском кладбище, ставшем известным с 17-го века, была построена церковь. Проект этого здания принадлежит архитектору Аврааму Мельникову, который разработал его специально для постройки объектов культовой архитектуры в Северо-Западном крае.

На сегодняшний день на этом месте находится комплекс храмов, включающий в себя не только церковь Марии Магдалины, но и крестильную церковь Иоанна Предтечи, построенную в 1992 году, и часовню, возведенную в 1998 году в честь всех белорусских святых. Примечательно, что традиция дарения пасхальных яиц связана именно с именем святой равноапостольной Марии Магдалины. Церковь, освященная в ее честь, представляет собой уникальный архитектурный объект, поскольку сочетает в себе элементы позднего классицизма и emerging retrospective-Russian style, что делает ее одним из немногих примеров архитектуры переходного периода. В конце 19 века перед ней была построена брама с иконами в нишах, которая сохранилась до наших дней.

С 1933 года церковь неоднократно закрывали, превращая в склад для хранения картофеля или столярную мастерскую, и даже разместили в ней архив в 1950-м, изменив интерьер и фасады. Интересно, что в одном из фильмов церковь «сыграла» роль штаб-квартиры фашистского гауляйтера Кубе.

Храм, некоторое время простоявший заброшенным, вернули епархии в 1990 году, сделав его первой церковью в Минске, возвращенной верующим. За семь месяцев удалось восстановить здание, и для реставрации фресок был приглашен греческий мастер. 25 ноября 1990 года в столице прошел первый за десятилетия крестный ход, в рамках которого в храм была перенесена частица мощей Марии Магдалины.