Церковь Святого Павла была построена по предложению королевы Аделаиды, вдовы Вильгельма IV, которая провела зиму 1838–1839 гг. на Мальте. Поскольку британцы не могли ходить в местные храмы, королева просила основать Монастырскую церковь в англиканской традиции. До этого англиканские службы проходили в зале во Дворце Великого Магистра, но, по заявлению королевы, это было "недостаточно, чтобы удовлетворить потребности первейшей из английских семей."
Британское правительство предоставило под строительство земли – на месте, где прежде стоял Auberge d'Allemagne – конвентуальный дом немецких рыцарей–госпитальеров. Королева Аделаида оплатила постройку и заложила первый камень в фундамент 20 марта 1839 года.
Здание предполагалось строить по проекту Ричарда Ланкашира, но оно оказалось неустойчивым, и работа снова началась в 1841 году под руководством Уильяма Скампа.
Церковь была посвящена Святому Павлу, апостолу и первому христианскому миссионеру на Мальте, потерпевшему кораблекрушение на острове в 59–60 гг. от Р.Х. План предусматривал сооружение высокого алтаря за западе и четыре боковые двери. Епископ Гибралтара настаивал на более ортодоксальном макете с алтарем на востоке, поэтому Скампу пришлось выстроить апсиду внутри больших дверей, чтобы поддержать святилище.
До Второй Мировой войны церковь еще несколько раз обновлялась и достраивалась, а во время войны ее площади служили в качестве бомбоубежища для церковных служителей, их семей и простых граждан.
Несмотря на тяжелые бомбардировки Валлетты во время Второй мировой войны и уязвимое положение собора, он избежал серьезных повреждений во время воздушных налетов 1941-1942 гг., хотя после бомбардировок стеклянные окна пришлось полностью заменить. С этих времен на стенах церкви размещены мемориальные дубовые панели, посвященные всем подразделениям военно-морского флота, сухопутным войскам и ВВС.
Интерьер церкви довольно суров, но здесь есть и колонны, и пилястры с каннелюрами, а венчают их коринфские капители, поддерживающие карниз. Дальнейшие ремонтные работы после войны побудили вернуться к исходной ориентации алтаря по проекту Скампа – западный предел был преобразован в хор, создавая новый каменный экран нефа. Прежний каменный амвон и аналой заменены деревянными, и представлены как мемориал сэру Уинстону Черчиллю.
С 2000 г. реконструкции сооружения проводились уже несколько раз: обновлялась позолота, устанавливались новые фрагменты, освещение, дополнительные архитектурные надстройки, совершенствовалась хозяйственная часть здания. Сегодня в церкви установлены информационные щиты с подробной историей здания, а также улучшена гостевая система, ориентированная на приезжих посетителей и паломников.
