Закладка приходского храма по проекту архитектора Д. Кваренги состоялась весной 1781 г. в присутствии цесаревича Павла Петровича с супругой Марией Федоровной, великих князей Александра и Константина. По окончании строительства 6 сентября 1784 г. митрополит Санкт-Петербургский и Новгородский Гавриил Петров произвел освящение. Торжества проходили в присутствии великих князей, пожертвовавших храму свои венчальные иконы Апостола Павла и Святой Равноапостольной Марии Магдалины, в честь которой была наречена великая княгиня Мария Федоровна при переходе в православие.
Строительству церкви и планировке местности вокруг нее уделялось особое внимание. Значение храма как духовного и архитектурного центра селения отражено в его архитектурно-планировочной и объемной композиции. Величественная постройка с протяженными по оси север-юг фасадами занимает доминирующее положение. Восточным фасадом она включена в композицию парка у Колоннады Аполлона, входя в систему важнейших визуальных связей Большого дворца. Западным фасадом с портиком здание ориентировано в сторону центральной городской площади Павловска.
Прямоугольная в плане площадь сыграла важную роль в формировании исторической градостроительной структуры Павловска конца XVIII – первой трети XIX в. Центральное пространство площади занимал луг – «парадное место», по периметру обнесенный «перилами», низкой оградой из балясин. Луг на площади являлся особым предметом внимания августейших владельцев, объявивших в 1794 г.: «Всем здешней дачи жителям подтверждается, чтобы по парадному перед церковью месту, огороженному перилами, ходить и дорогу прокладывать никто не отваживался и тем бы не портили вид этому лугу; поелику проложенные тем лугом дороги Их Императорским Высочествам видеть противны быть могут». Широкая аллея из лип окаймляла площадь с трех сторон, впоследствии получив название улицы Под Липками, ныне – улица Просвещения.
На площади рядом с храмом в 1781–1784 гг. архитектор Д. Кваренги возвел одноэтажное приходское
Церковь Святой Равноапостольной Марии Магдалины является одним из лучших образцов строгого классицизма в Петербурге. Здание привлекает необычностью и своеобразием своей архитектуры. Это первый опыт по возведению православного храма итальянским архитектором Д. Кваренги, приехавшим в Петербург из Рима по приглашению Екатерины II в начале 1780 г.
Симметричная центральная объемно-пространственная композиция обладает совершенными пропорциями. Выразительный ступенчатый силуэт акцентирован легкой ротондой колокольни, возвышающейся над центральным кубическим объемом. Архитектурное убранство отличается изысканной строгостью и равноценным характером решения главного западного и восточного фасадов, что соответствует важному градостроительному значению постройки. Боковые крылья – своеобразное архитектурное оформление северного и южного притворов, лестницы из которых вели на хоры и колокольню. В коньке они изначально были равны по высоте портикам паперти и апсиды, фланкируя здание с севера и юга. Южный и северный фасады первоначально завершал мезонин с трехчастным полуциркульным окном. Этот прием послужил образцом для частной застройки Павловска, где многие жилые дома имели подобное решение. Ведущая роль в оформлении принадлежит колонным портикам тосканского ордера и дорическому фризу с метопами и триглифами, придающими строгость и торжественность облику храма.