Der FrankfurterCäcilien-Verein gab Mendelssohn 1831 vor seiner großen Reise nach Paris ein Paulus-Oratorium in Auftrag. 1832 begann er die Arbeit nach seiner Rückkehr nach Berlin. Inspiriert von Bach und Händel, wünschte Mendelssohn sich von seinem Freund Julius Schubring einen Text aus Bibelworten sowie die Einbeziehung von Chorälen „aus dem Gesangsbuch […] ganz in der Art der Bachschen Passion“ (Brief an Julius Schubring, 22. Dezember 1832).
Adolf Bernhard Marx, der auch an dem Werk beteiligt war, hatte Einwände dagegen, bezeichnete die Choräle als verfehlt, doch Mendelssohn blieb bei seinem Vorhaben. 1834 war der Text fertig, so dass Mendelssohn mit der Komposition beginnen konnte. Er wurde jedoch bis zur geplanten Uraufführung im Frühjahr 1836 nicht fertig. Stattdessen fand sie einige Wochen später zu Pfingsten beim 18. Niederrheinischen Musikfest 1836 in Düsseldorf in der Tonhalle statt. Mendelssohn überarbeitete danach das Werk noch einmal für den Druck. In dieser endgültigen Fassung wurde es in englischer Sprache als St. Paul im Oktober 1836 in Liverpool aufgeführt. In den folgenden achtzehn Monaten wurde es auch beim Birmingham Triennial Music Festival und insgesamt über 50 weitere Male dargeboten.
Mendelssohn traf eine gezielte Auswahl darüber, welche Szenen er in seinen Paulus hineinnehmen wollte. Das Oratorium, in zwei Teile gegliedert, beschreibt den Werdegang vom Saulus zum Paulus, wobei der erste Teil seine Verfolgung der Christen (Märtyrertod des Stephanus durch Steinigung) schildert und das Damaskuserlebnis der Erscheinung Christi. Der zweite Teil erzählt von seiner Arbeit als Missionar und von den damit verbundenen Gefahren.
Dass Mendelssohn dramatisch besonders wertvolle Szenen, wie die im Kerker von Philippi und die des Tribunals von Caesarea, nicht verwendet hat, wurde oft bedauert, doch ging es ihm wahrscheinlich eher um die Umsetzung und Erzählung der Apostelgeschichte als um die Darstellung von Paulus als Persönlichkeit. Im zweiten Teil kommt der Ton dem einer Predigt sehr nahe. Im Schlusschor zieht Mendelssohn das Fazit, dass nicht nur Paulus die Gerechtigkeit Gottes durch seine Standhaftigkeit erfährt, „sondern alle, die seine Erscheinung lieben“. Somit stellt das Oratorium auch eine Aufforderung zur Bekehrung dar.
Martin Albrecht-Hohmaier: Mendelssohns Paulus: Philologisch-analytische Studien (= Musikwissenschaft an der Technischen Universität Berlin, 2). Mensch-und-Buch-Verlag, Berlin, 2004, ISBN 978-3-89820-595-5 (Dissertation an der TU Berlin, 2003)
Partitur des Paulus (Felix Mendelssohn-Bartholdys Werke, Partitur, Bd.: 13,85. Serie 13, Oratorien. Nr. 85, hrsg. von Julius Rietz, Leipzig: Breitkopf & Härtel).