Församlingen grundades 1881 och är därmed den äldsta landsortsförsamlingen i Sverige. Sedan tidigare fanns församlingar bara i Stockholm, Göteborg och Malmö. Jesuitprästerna i Stockholm, som hade ansvar för den katolska själavården i mellersta och norra Sverige, hade tidigare sporadiskt firat mässa och hört bikt i Gävle, men nu ansågs tiden mogen att ta nästa steg.
Grundare och den första kyrkoherden var pater Giovanni Moro från Genua i Norditalien.
Pater Moro, som bl.a. varit änkedrottningen Josefinas biktfader, tillhörde Barnabitordern. Barnabiternas verksamhet är inspirerat av den helige Paulus gärning, och det var därför givet att församlingen och dess kyrka skulle namnges efter aposteln och ha denne som skyddspatron. Till sin hjälp fick pater Moro efter ett par år orderbrodern pater Paolo Fumagalli som kaplan.
Det fanns ett trettiotal katoliker i Gävle – utländska hantverkare, slaktare, korgmakare och musiker – men mässa firades också på vallonbruken i Norduppland. Församlingen omfattade till en början även Dalarna och Norrland. Tanken var att man med utgångspunkt från Gävle skulle bilda nya församlingar i de många hamnstäderna i norra Sverige.
Kyrkan ritades av Hjalmar Gottfrid Sandels, som var biträdande stadsarkitekt i Gävle och senare blev slottsarkitekt i Stockholm. Den byggdes i det sena 1800-talets modestil nygotik och uppfördes i rött tegel med spetsbågefönster, strävpelare och en fristående portal. Invigningen skedde den 7 augusti 1881. En stor del av inventarierna kom från änkedrottningen och handbroderade mässkrudar kom från slottskapellet i Stockholm.
Samtidigt som pater Moro kom till Gävle, anlände några josefssystrar från Frankrike till staden. Här startade de Franska Skolan.
1886 lämnade pater Fumagalli församlingen och året efter flyttade pater Moro och josefssystrarna till Frankrike. Moro återvände dock till Gävle varje år fram till sin död 1904. Några år tidigare hade gävlekonstnärinnan Ida Matton utfört en byst av honom, som allltjämnt står i kyrkan.
Ny kyrkoherde blev den tyske jesuitpatern Bernhard Stolberg, som tidigare bl.a. varit präst i Malmö.
Från 1892 verkade Elisabethsystrarna i församlingen. De bedrev omfattande sjuk- och åldringsvård och deras insatser under spanska sjukan 1918-1919 var oumbärliga. 1933 förvärvade de fastigheten på Brynäsgatan 16, där de drev sjukhem fram till 1973. Där firades också mässa tre dagar i veckan.
I Sörforsa utanför Hudiksvall i Hälsingland byggdes 1909 ett kapell där prästerna i Gävle regelbundet firade mässa. 1924 blev Sörforsa en annexförsamling som omfattade hela Norrland. När det senare bildades nya församlingar i Sundsvall, Umeå och Luleå förlorade Sörforsa sin roll och 1964 återfördes de till S:t Pauli som kapellförsamling till Gävle.
Under 1980- och 1990-talen växte församlingens medlemsantal kraftigt och den gamla kyrkan ansågs för liten. Dessutom var den dyr att underhålla och renovera. Därför togs beslutet att bygga en helt ny kyrka.
Den gamla kyrkan övergavs 2000 och en ny kyrka började uppföras i kvarteret Skokloster på Söder. Den ritades av Derek Lewis, stadsarkitekt i Sandviken och dessutom aktiv medlem i församlingen. Byggnadens arkitektur speglar den”nya” liturgin som promulgerades år 1969 av den helige påven Paulus VI.
Den nya kyrkan invigdes och konsekrerades av biskop Anders Arborelius OCD den 7 september 2003.
Sedan 2016 finns även en kyrka i Ovanåker och sedan 2018 i Sandviken.
Patrik Öbrink
