Центральным ядром композиции является квадратное в плане помещение собственно церкви, перекрытое крестовым сводом на подпружных арках. Северные и южные двери храма раскрывались в «церковный коридор», где находилась лестница на хоры и колокольню. «Церковный коридор» предназначался для благотворительного учреждения, известного под именем «Мариинский госпиталь», или «Церковный инвалид», оно включало богадельню и больницу для горожан (поэтому в трудах, посвященных творчеству Кваренги, церковь неточно называют «госпиталем и богадельней»). Здесь же впоследствии находились квартиры причта.
В интерьере храма, освещенном полуциркульными окнами верхнего света, чудом сохранилась живопись, современная постройке и принадлежащая, предположительно, мастеру перспективной живописи художнику Ф.Д. Данилову. В алтарной апсиде помещена композиция с изображением Саваофа, на сводах и над хорами – заключенные в медальоны образы евангелистов, изображения разных святых, и среди них – Святой Равноапостольной Марии Магдалины.
Под хорами в западной стене симметрично по сторонам входной двери находятся памятники Н.И. Панину и А.Б. Куракину. Они представляют собой две одинаковые двухъярусные гранитные пирамиды, встроенные в стену. Нижний ярус оформлен двухколонным мраморным портиком с акротериями, в центре которого – посвятительные надписи. В верхнем ярусе пирамиды помещались рельефные медальоны из мрамора с портретными изображениями. У северной стены находится памятник Н.А. Загряжскому. В литературе все три памятника ошибочно упоминаются как «надгробные».
Однако в действительности графа Н.И. Панина, государственного деятеля, дипломата и воспитателя императора Павла I, в 1783 г. погребли в усыпальнице Благовещенской церкви Александро-Невской лавры в Петербурге (надгробие работы скульптора И.П. Мартоса с вероятным участием архитектора Д. Кваренги). Памятник в церкви Святой Марии Магдалины установили в 1797 г. по повелению императора Павла с надписью: «Граф Никита Иванович Панин родился 1718 года сентября 15 дня, скончался 1783 года марта 31 числа».
Памятник А.Б. Куракину с надписью «Другу супруга моего» установили в 1819 г. по приказанию вдовствующей императрицы Марии Федоровны. А.Б. Куракин, канцлер российских орденов, действительный тайный советник и член Государственного Совета, в детстве находился под особым покровительством своего дяди, графа Н.И. Панина, воспитывался вместе с будущим императором Павлом и был его другом, вследствие чего пользовался особым расположением Марии Федоровны. Он скончался в Веймаре 24 июня 1818 г. Находится ли захоронение Куракина в этом месте, достоверно не известно.
В 1821 г. в церкви похоронили Н.А. Загряжского, одного из воспитателей императора Александра I. Памятник установили по повелению Марии Федоровны в 1824 г. на средства племянницы Загряжского графини М.В. Кочубей. Он размещен в северной стене храма и представлял собой двухъярусную усеченную пирамиду с мраморной доской в нижней части, содержащей посвятительную надпись следующего содержания: «Здесь лежит тело двора Его Императорского Величества обер-шенка действительного камергера и орденов Св. Александра Невского и Св. Анны кавалера Николая Александровича Загряжского, родившегося 2-го апреля 1746 г., скончавшегося 23 июля 1821 г. Тленный памятник нетленным воспоминаниям кротости любви, в горести разлуки, в уповании вечного соединения, от сердца благодарного, от души благоговеющей положила Гр. М. Кочубей». В верхней части памятника помещалась доска из мрамора с рельефной композицией работы скульптора И.П. Мартоса, которая в настоящее время находится в экспозиции Павловского дворца-музея.
Облик здания за его длительную историю несколько изменился. В 1808–1809 гг. Кваренги сделал пристройки для лестничных клеток по сторонам портика паперти. Вид их фасадов со временем был значительно упрощен, важные детали отделки утрачены. Он же перестроил мезонины боковых флигелей церковного здания, превратив их в более полноценный, хотя и невысокий второй этаж. Конек крыши при этом сохранился на прежнем уровне, но восточная и западная фасадные стены были подняты, изменился также угол наклона крыши, которая стала более пологой.