De eerste kerk die op deze locatie gebouwd werd droeg de naam van Paulus de Heremiet, een kennis van Antonius van Egypte. De kerk hoorde bij het Eligiusklooster, opgericht door de heilige Eligius en Dagobert I. Dit klooster stond op de plaats waar nu het Parijse Paleis van Justitie staat. Vanaf daar begaf men zich per bootje naar de begraafplaats van de gemeenschap, waar de monniken werden begraven. Deze begraafplaats is in de loop der tijd in de vergetelheid geraakt en bestaat nu niet meer.
De eerste steen van de huidige kerk werd gelegd door koningLodewijk XIII in 1627. De kerk was bedoeld als thuisbasis voor de jezuïeten, en werd in het begin Église Saint-Louis de la Maison Professe des Jésuites (Sint-Lodewijk van het Belijdenishuis der Jezuïetenkerk) genoemd, refererend aan het aangrenzende Maison Professe des Jésuites
In de Saint-Paul zijn zowel Italiaanse als Franse elementen terug te vinden. Het gebouw wordt weleens vergeleken met de Il Gesù in Rome, maar die is zowel in lengte als hoogte groter. Het ontwerp in de vorm van een Latijns kruis, de kleine dwarsbeuken, de korte apsis, de hoge ramen waardoor veel licht binnenkomt en de koepel op het kruispunt van de beuken zijn allen elementen van de vroeg-Italiaanse architectuur, zoals de gebouwen van Carlo Maderno. De hoogte (de koepel is meer dan 55 meter hoog) doet echter meer denken aan de Franse gotiek.
De façade is ook gebouwd in Italiaanse stijl, maar met de breedte en de versieringen zijn er ook Franse en Nederlandse ontwerpen in terug te vinden. De belangrijkste inspiratiebron voor het ontwerp was waarschijnlijk de façade van de Église Saint-Gervais-Saint-Protais, gebouwd in 1618 door Salomon de Brosse. De zuilen zijn naar Korinthisch ontwerp.
.jpg)
