Заложен в 1846 году по повелению императора Николая I в качестве приходского храма. Необходимость в его строительстве была вызвана быстрым ростом населения города в 1840-х гг. после того, как Гатчина стала центром ежегодных военных маневров и местом пребывания императора и членов императорской фамилии на время их проведения. До этого основной приходской церковью для горожан служила церковь св. апостола Павла при придворном госпитале, построенная в 1823 году.

Проект здания собора в русско-византийском стиле разработал архитектор Р.И.Кузьмин. Строился на средства государственного казначейства. Строительство окончено в 1852 году; собор освящен в июне того же года. Каменный, пятиглавый, крестообразный в плане. Главный придел в честь св. апостола Павла; правый – свв. равноапостольных царей Константина и Елены; левый – св. равноапостольной Марии Магдалины. Центральный купол – двенадцатигранный с шестью окнами. Боковые купола меньше по размеру, восьмигранные с четырьмя окнами. Два из них с западной стороны служили звонницами. Золоченые кресты изготовлены на Санкт-Петербургском гальванопластическом и литейном заводе. Сами купола по распоряжению Николая I остались не золочеными. Иконостасы в соборе изготовлены из греческого кипариса резчиком Скворцовым по рисунку археолога Ф.Г.Солнцева. Алтарные иконы и настенные росписи выполнены художниками П.М.Шамшиным, Ф.А.Бруни, А.Ф.Перницем, М.И.Скотти, А.А.Зеленским, В.А.Серебряковым, Ф.С.Завьеловым.

По штатам 1853 года собору полагалось иметь ключаря, 2-х священников, дьякона, 2-х псаломщиков, 2-х пономарей и просвирню. С 1876 года ключарь заменен штатным протоиереем, сокращена должность одного пономаря.

К собору были приписаны: часовня во имя Всех Святых на устроенном в 1851 году городском кладбище (в 1888-1889 гг. перестроена в каменную церковь по проекту архитектора Н.В.Дмитриева); часовня в память «чудесного спасения» императора Александра II при покушении Д.В.Каракозова 4 апреля 1866 г., построенная в 1868 году напротив госпиталя по Большому пр.; часовня «в память избавления государя императора Александра II от угрожавшей ему опасности» при покушении А.К.Соловьева 2 апреля 1879 г., построенная в 1879 году по Динабургскому шоссе в Александровской слободе.

Ежегодно 12 октября в собор из дворцовой церкви Св. Троицы крестным ходом переносились для поклонения верующим «мальтийские святыни» – религиозные реликвии, поднесенные мальтийскими рыцарями в дар императору Павлу I в 1799 году: часть древа Креста Господня, икона Филермской Богоматери и рука мощей Иоанна Крестителя. Реликвии постоянно хранились в соборе Зимнего дворца, откуда накануне празднования их доставляли из столицы в Гатчинскую дворцовую церковь для проведения богослужения и крестного хода.

С конца XIX века до 1908 года при соборе действовал отдельный эстонский причт из священника и псаломщика, совершавший службы на эстонском языке для проживающих в Гатчине православных эстонцев. С 1908 года в городе образован самостоятельный эстонский приход.

Здание собора ремонтировалось в 1854-1856, 1864-1868 и 1875 гг. В 1892 и 1915 гг. производился капитальный ремонт.

В 1867 году по проекту протоиерея о. В. Славинского при соборе открыто приходское попечительство для вспомоществования бедным. На основании высочайше утвержденного 4 июля 1874 г. устава стало именоваться Гатчинским благотворительным обществом. Находилось под покровительством императрицы. Обществу принадлежал детский приют для мальчиков и девочек, а также Андреевская богадельня для престарелых женщин.

В 1885 году при соборе открыт склад книг С.-Петербургского епархиального Братства Пресвятой Богородицы. В 1891 году построено 2-х этажное каменное здание, в котором открыта одноклассная церковно-приходская школа для детей беднейших жителей Гатчины, находившаяся в непосредственном ведении настоятеля собора. В 1896 году открыта вторая школа. В 1895 году по инициативе настоятеля собора о. Николая Судакова в Гатчине открыто отделение епархиального Братства Пресвятой Богородицы, устроены братский хор и хор певчих при соборе.

Декретом СНК от 23 января 1918 г. «Об отделении церкви от государства и школы от церкви» собор лишен прав юридического лица, его имущество подлежало национализации. В 1920 году в крипте (подземной галерее) собора устроен нижний храм во имя св. Иоанна Крестителя для служб в зимнее время. Собор закрыт в 1939 году. Здание собора является памятником архитектуры и охраняется государством.

Клировые ведомости (1853–1855; 1858–1896 гг.); исповедные росписи (1853–1862 гг.); акты обозрения собора благочинным (1881; 1890; 1892 гг.); документы об отводе участков земли в собственность собора для постройки церковных домов (1854–1884 гг.); документы о проведении ремонтных работ в здании собора, в т.ч.: указы С.-Петербургской духовной консистории, рапорты причта, протоколы заседаний временной строительной комиссии по исправлению собора, сметы, контракты с подрядчиками (1854–1856; 1864–1868; 1875; 1883 гг.); документы о разногласиях между причтами Павловского собора и дворцовой церкви св. Троицы по вопросам разграничения обязанностей и разделе прихода (1852-1875 гг.); книги прихода (1852–1903 гг.) и расхода (1880–1909 гг.) денежных сумм собора; книги прихода и расхода денежных сумм приписной к собору кладбищенской церкви Всех Святых (1900-1906 гг.).